二叉树04（leetcode110/257/404）

参考资料：

https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html

110. 平衡二叉树

题目描述：

给定一个二叉树，判断它是否是平衡二叉树

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

思路分析：

        递归，后序遍历（中间收集左右子节点的高度进行判断）。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public: 
    //节点高度
    int getHeight(TreeNode* node){
        if(node==nullptr) return 0;
        int leftHeight=getHeight(node->left);
        if(leftHeight==-1) return -1;
        int rightHeight=getHeight(node->right);
        if(rightHeight==-1) return -1;
        return abs(leftHeight-rightHeight) > 1 ? -1 : 1+max(leftHeight,rightHeight);
    }

    bool isBalanced(TreeNode* root) {
        if(getHeight(root)==-1) return false;
        return true;
    }

   
};

257. 二叉树的所有路径

 题目描述：

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

叶子节点 是指没有子节点的节点。

示例 1：

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

思路分析：

        递归，前序遍历（路径从根节点往后指）。

        回溯，参数使用引用，更方便展示回溯效果。

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void allPath(TreeNode* node,vector<int>& path,vector<string>& result){//引用，方便展示回溯过程
        path.push_back(node->val);//中，结束条件为遍历到叶子节点，所有得在返回结果前加入
        //终止条件
        if(node->left==nullptr && node->right==nullptr){
            string s;
            for(int i=0;i<path.size()-1;i++){
                s+=to_string(path[i]);
                s+="->";
            }
            s+=to_string(path[path.size()-1]);
            result.push_back(s);
            return;    
        }

        if(node->left!=nullptr){//左
            allPath(node->left,path,result);
            path.pop_back();//回溯
        }
        if(node->right!=nullptr){
            allPath(node->right,path,result);
            path.pop_back();//回溯
        }
    }

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

404. 左叶子之和

  题目描述：

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

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

思路分析：

        递归，后序遍历

代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr) return 0;
        if(root->left==nullptr && root->right==nullptr) return 0;//因为收集的是该结点的左叶子节点的数，如果该结点为叶子节点，就无左孩子了

        int leftNum=sumOfLeftLeaves(root->left);//左
        if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr)
            leftNum=root->left->val;
        int rightNum=sumOfLeftLeaves(root->right);//右
        int sum=leftNum+rightNum;//中
        return sum;
    }
};