代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和

110.平衡二叉树 

题目链接：110. 平衡二叉树 - 力扣（LeetCode）

思路：判断平衡二叉树，就是判断两个子树的高度差，继而问题转化为了如何求子树的高度——后序遍历（主要卡在了这里)。递归函数返回的是树的高度，同时用-1来表示退出递归（一开始想着用bool型作为返回值，发现函数不好设计）。同时要关注递归函数的返回条件，不要忘了用abs函数和max函数简化代码。

class Solution {
public:
    int geth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int lh = geth(root->left);
        int rh = geth(root->right);
        if (lh == -1) {
            return -1;
        }
        if (rh == -1) {
            return -1;
        }

        return abs(lh - rh) > 1 ? -1 : 1 + max(lh, rh);
    }
    bool isBalanced(TreeNode* root) {
        if (root == NULL)
            return true;
        return geth(root) == -1 ? false : true;
    }
};

257.二叉树的所有路径

题目链接：257. 二叉树的所有路径 - 力扣（LeetCode）

思路：困难在找到一条路径后如何进行回溯。解决方法是用path数组存储路径，在找到一条路径后输出path，并弹出一个元素，若没找到路径则进行递归。注意，string类型可以直接和int类型拼接，但int不会自动转化为char，因此要借助to_string()方法。

这里借助传递参数的引用来实现递归，并没有使用函数返回值。

class Solution {
public:
    void traversal(TreeNode *root,vector<string>&result,vector<int>&path){
        path.push_back(root->val);
        if(root->left==NULL&&root->right==NULL){
            string str;
            for(int i=0;i<path.size()-1;i++){
                str+=to_string(path[i]);
                str+="->";
            }
            str+=to_string(path[path.size()-1]);
            result.push_back(str);
            return;
        }
        if(root->left){
            traversal(root->left,result,path);
            path.pop_back();
        }
        if(root->right){
            traversal(root->right,result,path);
            path.pop_back();
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if(root==NULL)return result;
        traversal(root,result,path);
        return result;
    }
};

404.左叶子之和 

题目链接：404. 左叶子之和 - 力扣（LeetCode）

思路：求所有左叶子节点的和。但是我们必须根据其父节点才能确认其是否为左叶子，故我们递归也只递归到左叶子的父节点。

同时我们把求整棵树的左叶子节点之和变为分别求左右子树左叶子节点之和再相加。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
           if(root==NULL)return 0;
           if(root->left==NULL&&root->right==NULL)return 0;
           int lc=sumOfLeftLeaves(root->left);
           if(root->left&&!root->left->left&&!root->left->right){
               lc+=root->left->val;
           }
           int rc=sumOfLeftLeaves(root->right);
           return lc+rc;
    }
};