Day11: 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 222.完全二叉树的节点个数

---

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

/**
 * 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 gethigh(TreeNode* root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int left=gethigh(root->left);
        if(left==-1)
        {
            return -1;
        }
        int right=gethigh(root->right);
        if(right==-1)
        {
            return -1;
        }
        if(abs(left-right)>1)
        {
            return -1;
        }
        return left>right?left+1:right+1;
    }
    //求节点差值
    bool isBalanced(TreeNode* root) {
        return gethigh(root)==-1?false:true;
    }
};

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

/**
 * 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 count(TreeNode*root,vector<int>&vec,vector&res)
    {
        if(root==nullptr)
        {
            return ;
        }
        //如果不是空
        vec.push_back(root->val);//记录经过的路径
        count(root->left,vec,res);
        if(root->right==nullptr&&root->left==nullptr)
        {
            string s;
            for(int i=0;isize()-1;i++)
            {
                s+=to_string(vec[i]);
                s+="->";
            }
            s+=to_string(vec[vec.size()-1]);
            res.push_back(s);
            //vec.pop_back();
        }
        count(root->right,vec,res);
        vec.pop_back();
    }
    vector binaryTreePaths(TreeNode* root) {
        //回溯
        vector<int> vec;
        vector res;
        count(root,vec,res);
        return res;
    }
};

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

/**
 * 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 sumleft(TreeNode*root)
    {
        if(root==nullptr)
        {
            return 0;
        }
         int lsum=sumleft(root->left);
        if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr)
        {
           lsum = root->left->val;//注意根节点左子树只有一个节点的情况
        }
       
        int rsum=sumleft(root->right);
        return lsum+rsum;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        return sumleft(root);
    }
};

题目222. 完全二叉树的节点个数 - 力扣（LeetCode）

/**
 * 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 count(TreeNode* root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int left=count(root->left);
        int right=count(root->right);
        return left+right+1;
    }
    int countNodes(TreeNode* root) {
        return count(root);
    }
};

---

最后

二叉树的所有路径，第一次接触回溯题目，需要再多写几遍

注意二叉树的高度和深度是怎么求，递归法需要安全掌握，迭代法二刷的时候过一遍