110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

class Solution {
public:
    int getDeepth(TreeNode *root) {
        if (root == nullptr) return 0;
        return 1 + max(getDeepth(root->left), getDeepth(root->right));
    }
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        int lDeepth = getDeepth(root->left);
        int rDeepth = getDeepth(root->right);
        if (abs(lDeepth - rDeepth) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

注意点：

1.求绝对值函数abs()
2.递归三部曲

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：

paths-tree.jpg

输入：**root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

class Solution {
public:
    string getResultString(vector<int>& path) {
        string result = "";
        for(int i = 0; i < path.size()-1;i++) {
            result = result + to_string(path[i]) + "->";
        }
        result = result + to_string(path[path.size()-1]);
        return result;
    }
    void travelsal(TreeNode* root, vector<int>& path, vector<string>& result) {
        path.emplace_back(root->val);
        if (root->left == nullptr && root->right == nullptr) {
            string resultString = getResultString(path);
            result.emplace_back(resultString);
            return;
        }

        if(root->left) {
            travelsal(root->left, path, result);
            path.pop_back();
        }
        if(root->right) {
            travelsal(root->right, path, result);
            path.pop_back();
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        if(root == nullptr) return result;
        travelsal(root, path, result);
        return result;
    }
};

注意点：
1.涉及这种二叉树路径求解，一般使用回溯法

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right== NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左
        if (root->left && !root->left->left && !root->left->right) { // 左子树就是一个左叶子的情况
            leftValue = root->left->val;
        }
        int rightValue = sumOfLeftLeaves(root->right);  // 右

        int sum = leftValue + rightValue;               // 中
        return sum;
    }
};

注意点：
1.递归三部曲、左叶子节点的判断