剑指OfferJZ39：平衡二叉树-java版

雨点打透心脏的1/2处 2023-01-21 14:16 4阅读 0赞

### 剑指OfferJZ39：平衡二叉树-java版 ###

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

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

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。  
二叉排序树：对于每一个节点，当前节点大于左子树的所有节点，小于右子树的所有节点  
要判断是否为二叉树需要满足两个条件：  
1.二叉树是否为二叉排序树  
2.对于二叉树的每个节点，它的左右两个子树的高度差的绝对值是否<1  
牛客这道题已经默认是二叉排序树了，所以不用进行条件1的判断

public class Solution { 
        private  boolean ans;
        public boolean IsBalanced_Solution(TreeNode root) { 
            if(root==null){ 
                return true;
            }
            ans=true;//标记左右子树的高度差是否为1
            TreeDepth(root);
            return ans;
    
        }
        private int TreeDepth(TreeNode node){ 
    
            if(node==null){ 
                return 0;
            }
            if(ans) { //ans=true
                //当前节点左子树高度
                int leftDepth = TreeDepth(node.left);
                //当前节点右子树高度
                int rightDepth = TreeDepth(node.right);
                if (Math.abs(leftDepth - rightDepth) > 1) { 
                    ans = false;
                }
                //返回当前节点距离叶子节点的长度（方便其它节点计算左右子树的高度）
                return Math.max(leftDepth,rightDepth)+1;
            }
            return 0;//这个地方返回什么已经不重要了，因为我们已经找到一个节点不满足条件了
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210526112755476.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221020/90fd6400eb65465d966936be0e4bbf76.png
[20210526112755476.gif_pic_center]: /images/20221020/d43cf33e14da46a08fbc1ccc39d7660e.png