力扣-110题平衡二叉树（C++）- 递归+有价值

快来打我* 2022-09-16 00:15 161阅读 0赞

题目链接：[https://leetcode-cn.com/problems/balanced-binary-tree/][https_leetcode-cn.com_problems_balanced-binary-tree]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][bb1d4a33fa804de384b66a218755d4c2.png]

/**
     * 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:
        bool isBalanced(TreeNode* root) {
        
            return dfs(root)>=0;
        }
        int dfs(TreeNode* root){
        
            if(root==NULL) return 0;
    
            int left=dfs(root->left);//因为要计算左右孩子的高度，递归需要整型来计算，所以，dfs函数不能返回值为bool
            int right=dfs(root->right);
    
            if(left>=0&&right>=0&&abs(left-right)<=1) return max(left,right)+1;
            else return -1;
        }
    };

[https_leetcode-cn.com_problems_balanced-binary-tree]: https://leetcode-cn.com/problems/balanced-binary-tree/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/38bbeb872b82417c8e518bc839c20c86.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c797512b5bae47ea9fbe11a13fc1d7ce.png
[bb1d4a33fa804de384b66a218755d4c2.png]: /images/20220828/afb67cecd8f240c99450fe8f6ced4c90.png