110.平衡二叉树

求深度适合用前序遍历，而求高度适合用后序遍历。

巧妙设计递归三部曲中返回值的意义，比如这题返回-1就是非平衡，返回height就是平衡且还能计算高度，一举两得，如果返回值设计成bool那实际上不好计算每一次递归左右节点的高度，还是要算高度，返回height和-1就包含了bool的意思。

//C++
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        int height = getHeight(root);
        return height == -1 ? false : true;
    }
    int getHeight(TreeNode* cur) {
        if (cur == nullptr) return 0;
        int left = getHeight(cur->left);
        if(left == -1) return -1;
        int right = getHeight(cur->right);
        if (right == -1) return -1;
        if (abs(left - right) > 1) return -1;
        else return max(left, right) + 1;
    }
};
//C#
public class Solution {
    public bool IsBalanced(TreeNode root) {
        return getHeight(root) == -1 ? false : true;
    }
    public int getHeight(TreeNode cur) {
        if (cur == null) return 0;
        int left = getHeight(cur.left);
        if (left == -1) return -1;
        int right = getHeight(cur.right);
        if (right == -1) return -1;
        if (Math.Abs(left - right) > 1) return -1;
        return Math.Max(left, right) + 1;
    }
}

这题有点特殊，在单层递归里也还在return，实际上可以单独开一个标志量记录是否平衡。

public class Solution {
    bool res = true;
    public bool IsBalanced(TreeNode root) {
        getHeight(root);
        return  res;
    }
    public int getHeight(TreeNode cur) {
        if (cur == null) return 0;
        int left = getHeight(cur.left);
        int right = getHeight(cur.right);
        if (Math.Abs(left - right) > 1) res = false;
        return Math.Max(left, right) + 1;
    }
}

257. 二叉树的所有路径

使用前序遍历（这样才是由根节点->子节点的顺序）进行遍历，每下一层路径记录+一个节点，到达叶子节点就把新路径加到结果集里，注意递归回退时要回溯把路径记录弹出一个节点。

注意返回条件为叶子节点，同时单层递归的条件还要保证避免出现引用空指针，有时候返回条件是控制cur!=null，有时候是控制到叶子结点弹出，比如输出路径（day18路径和也是这样），要注意这种技巧。

//C++ 代随，无全局变量，本质也是用引用传参和全局变量效果一样
// 版本一
class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中，中为什么写在这里，因为最后一个节点也要加入到path中 
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) { // 左 
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};
//C++ 全局变量有回溯
class Solution {
public:
    vector<int> path;
    vector<string> result;
    vector<string> binaryTreePaths(TreeNode* root) {
        if (root == nullptr) return result;
        traversal(root);
        return result;
    }
    void traversal(TreeNode* cur) {
        path.push_back(cur->val);
        if (cur->left == nullptr && cur->right == nullptr) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
          	return;
        }
        if (cur->left) {
            traversal(cur->left);
            path.pop_back();
        }
        if (cur->right) {
            traversal(cur->right);
            path.pop_back();
        }
      return;
    }
};

//C# 全局变量无回溯
public class Solution {
    public List<string> result = new List<string>();
    public IList<string> BinaryTreePaths(TreeNode root) {
        if(root == null) return result;
        List<int> path1 = new List<int>();
        doit(root, path1);
        return result;
    }
    public void doit(TreeNode cur, List<int> path1) {
        List<int> path = new List<int>(path1);
        path.Add(cur.val);
        if (cur.left == null && cur.right == null) {
            string sPath = new string("");
            for (int i = 0; i < path.Count - 1; i++) {
                sPath += path[i].ToString();
                sPath += "->";
            }
            sPath += path[path.Count - 1].ToString();
            result.Add(sPath);
            return;
        }
        if (cur.left != null) doit(cur.left, path);
        if (cur.right != null) doit(cur.right, path);
        return;
    }

}

C#中List本身是引用类型，递归不同层操作的实际是同一个List，所以这里List path = new List(path1); 拷贝一份副本，来模拟实现C+里的复制，path也就不需要回溯了，没层递归修改的path没有关系。可以看看下面的解释。

alt

404.左叶子之和

层序遍历在加入左子节点的时候判断一下是不是叶子结点（左右节点都为空）。

 //C++
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        queue<TreeNode*> que;
        int sum = 0;
        if (root == nullptr) return 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left != nullptr) {
                    que.push(cur->left);
                    if (cur->left->left == nullptr && cur->left->right == nullptr)
                    sum += cur->left->val;
                }
                if (cur->right != nullptr) {
                    que.push(cur->right);
                }
            }
        }
        return sum;
    }
};

递归，判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。所以递归函数的每一层实际上是当前节点的子节点的左叶子数，并判断当前节点的左节点是不是叶子，加上右子节点的左叶子数，就得到了这个节点的所有左叶子数，也就是还没有遍历到子节点就提前在父节点处理。


public class Solution {

    public int SumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;     
        return doit(root);;
    }
    int doit(TreeNode cur) {
        if (cur == null) return 0;
        if (cur.left == null && cur.right == null) return 0;
        int left = doit(cur.left);
        if (cur.left != null && cur.left.left == null && cur.left.right == null) {
            left = cur.left.val;
        }
        int right = doit(cur.right);
        int sum = left + right;
        return sum;
    }
}

[代码随想录一刷] day17 二叉树

110.平衡二叉树

257. 二叉树的所有路径

404.左叶子之和