C语言重构【110】平衡二叉树

左手的ㄟ右手 2022-12-08 15:30 171阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树，判断它是否是高度平衡的二叉树。
    
    本题中，一棵高度平衡二叉树定义为：
    
    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
    
    示例 1:
    
    给定二叉树 [3,9,20,null,null,15,7]
    
        3
       / \
      9  20
        /  \
       15   7
    返回 true 。
    
    示例 2:
    
    给定二叉树 [1,2,2,3,3,null,null,4,4]
    
           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    返回 false 。

#### 方案： ####

*  深度优先遍历

#include <iostream>
    #include <math.h>
    struct TreeNode
    { 
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) { }
    };
    class Solution { 
    public:
        bool isBalanced(TreeNode* root) { 
            return funDepth(root)==-1?false:true;        
        }
        
         int funDepth(TreeNode* root) { 
            if(root==NULL) return 0;
            if(root->left==NULL&&root->right==NULL) return 1;
            else { 
                int depthl = funDepth(root->left);
                int depthr = funDepth(root->right);
                
                //如果平衡，则返回深度，否则返回-1
                if(depthr!=-1&&depthl!=-1&&abs(depthr-depthl)<=1) return max(depthr,depthl)+1;
                else return -1;
            }
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode