LeetCode 110 平衡二叉树

递归写法很简单，直接自底向上每个节点判断是否为空，为空说明该层高度为0。不为空用一个int型变量l记录左子树高度（递归调用该函数自身），一个int型变量r记录右子树高度（同样递归调用该函数自身），将l和r相减取绝对值，大于1说明不平衡直接返回-1，此外还需要判断l和r是否已经是-1，这种情况下也直接返回-1。这样判断的底层原理是计算每个节点返回值是高度还是-1，取-1也是因为不会影响到正常高度的计算。最后来到递归遍历阶段，返回1+max(l,r)即可。

这个过程中，最上层是确认返回条件，中间是确认参数和返回值，最下层是递归逻辑。

代码如下：

class Solution {
public:
    int height(TreeNode* root) {
        if (!root) return 0; 
        int l = height(root->left), r = height(root->right);
        if (abs(l - r) > 1) return -1;
        else if (l == -1) return -1;
        else if (r == -1) return -1;
        return 1 + max(l, r); 
    }
    bool isBalanced(TreeNode* root) {
        if (height(root) != -1) return true;
        else return false;
    }
};

LeetCode 257 二叉树的所有路径

这题对于学过回溯法的人来说，很明显是回溯了。新手可能会有点头痛。

回溯法本质上也是一种递归，是一种暴力枚举。在递归过程中，如果没有后续状态就会把当前这一条路径放进存储结果的集合中，返回当前函数到上一层。而如果有后续状态，就先记录当前路径，将当前路径加上其中一个下一状态，用这一路径继续递归，直到返回，在其语句后面还要将路径还原至递归前。相当于先给你一个苹果，让你吃完之后看苹果是啥样子，记录下来，再一路回到你吃苹果之前，把苹果给别人吃，看又是啥样子。这样的递归过程就能实现一种暴力枚举。

代码如下：

class Solution {
private:
    vector<string> res;
    string path = "";
public:
    void backtracking(TreeNode* cur) {
        if (!cur->left && !cur->right) {
            res.push_back(path);
        }
        else {
            if (cur) {
                string temp = path;
                if (cur->left) {
                    string s = to_string(cur->left->val);
                    path += "->";
                    path += s;
                    backtracking(cur->left);
                    path = temp;
                }
                if (cur->right) {
                    string s = to_string(cur->right->val);
                    path += "->";
                    path += s;
                    backtracking(cur->right);
                    path = temp;
                }
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if (!root) return res;
        string s = to_string(root->val);
        path += s;
        backtracking(root);
        return res;
    }

};

还需要注意的有递归起始状态，返回条件和每次递归逻辑的确定。

本题还可以尝试迭代法来写。暂时先放这，等会来写。

LeetCode 404 左叶子之和

其实前序遍历等遍历方式中选一种就行了，需要注意的是左叶子首先要是某个叶子的左节点，然后还要是叶子节点。可以顺便满足这个遍历情况的，前序遍历是肯定可以的。中序遍历也可以，层序遍历和后续遍历会比较麻烦一点。这里给出前序遍历实现的代码如下：

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