[每日一道小算法（三十九）] [二叉树] 平衡二叉树（剑指offer）

客官°小女子只卖身不卖艺 2023-07-06 06:20 33阅读 0赞

前言：  
这道题，一直AC出来，什么情况！！！！！ 解决了好久！！！！！ 呜呜呜呜！！！！！

### 题目描述 ###

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

### 解题思路 ###

先来了解一下平衡二叉树的概念：平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。  
了解了概念，我们就可以来解决这道题了，我们可以递归左右子树，并同时判断左右子树是否符合平衡树，不符合直接跳出。如果左子树和右子树的高度差大于1，说明以当前节点作为根节点的树不是平衡树，则直接返回false；如果左子树和右子树的高度差小于等于1，说明以当前节点作为根节点的树是平衡树，则递归判断对其左子树和右子树是否是平衡树。

### 代码样例 ###

public boolean IsBalanced_Solution(TreeNode root) { 
            return dept(root)!=-1;
        }
        public int dept(TreeNode root)
        { 
            if(root == null)
            { 
                return 1;
            }
            int left = dept(root.left);
            if(left==-1)
            { 
                return -1;
            }
            int right = dept(root.right);
            if(right == -1)
            { 
                return -1;
            }
            if((left-right)>1 || (left-right)<-1)
            { 
                return -1;
            }
            else { 
                return 1+(left>right?left:right);
            }
        }