剑指Offer-平衡二叉树

刺骨的言语ヽ痛彻心扉 2022-02-19 11:43 206阅读 0赞

## 题目描述 ##

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

**平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。**  
解题思路—**递归**：判断是否为平衡二叉树，肯定要得到各个子树的**深度**。所以**递归遍历每个结点，根据该结点的左右子树高度差判断是否平衡，然后再继续对左右子树进行判断**。这就是在求二叉树的深度上，加上了判断条件！如何**求二叉树深度**，可以参考[剑指Offer—二叉树的深度][Offer]！  
解题思路—**剪枝递归**：这是对上述递归方法的**优化**！**对二叉树进行了剪枝，如果子树不是平衡二叉树，则直接停止遍历，不用再额外判断其余子树是否为平衡二叉树。推荐！**

## Java解题—递归 ##

public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            if(root==null) return true;
            return Math.abs(CalNode(root.left)-CalNode(root.right))<2 
                    && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }
        
        // 计算子树的深度
        public int CalNode(TreeNode root){
            if(root==null) return 0;
            return Math.max(CalNode(root.left), CalNode(root.right))+1;
        }
    }

## Java解题—剪枝递归 ##

public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            return CalNode(root)!=-1;
        }
        
        public int CalNode(TreeNode root){
            if(root==null) return 0;
            int left = CalNode(root.left);
            if(left==-1) return -1;
            int right = CalNode(root.right);
            if(right==-1) return -1;
            return Math.abs(left-right)>1? -1 : Math.max(left, right)+1;
        }
    }

[Offer]: https://blog.csdn.net/gaoyueace/article/details/89322293