110平衡二叉树难度最大
剩下的两个就是朴素dfs

110. 平衡二叉树

不和条件返回-1。不然返回最大高度

class Solution {
public:
    // 不和条件了就是-1
    bool isBalanced(TreeNode* root) {
        return getHeight(root, 0) != -1;
    }

    int getHeight(TreeNode* root, int height)
    {
        if (root == nullptr) return height;
        int leftHeight = getHeight(root->left, height + 1);
        int rightHeight = getHeight(root->right, height + 1);
        if (leftHeight == -1 || rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : max(leftHeight, rightHeight);
    }
};

257. 二叉树的所有路径

class Solution {
public:
    vector<string> res;

    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root, "");
        return res;
    }

    void dfs(TreeNode *root, string s)
    {
        if (root == nullptr)
        {
            return;
        }
        if (root->left == nullptr && root->right == nullptr)
        {
            s += "->" + to_string(root->val);
            res.push_back(s.substr(2, s.size() - 2));
            return;
        }
        dfs(root->left, s + "->" + to_string(root->val));
        dfs(root->right, s + "->" + to_string(root->val));
    }
};

404. 左叶子之和

class Solution {
public:
    int res = 0;
    int sumOfLeftLeaves(TreeNode* root) {
        dfs(root);
        return res;
    }

    // 如何确定左节点?
    void dfs(TreeNode* root)
    {
        if (root == nullptr) return;
        if (root->left && root->left->left == nullptr && root->left->right == nullptr)
        {
            res += root->left->val;
        }
        dfs(root->left);
        dfs(root->right);
    }
};