题解 | #判断是不是平衡二叉树#

菜鸟的思路： 要求每个节点的左右子树高度差不超过1

1. 遍历每一个节点，每个节点都要满足:Math.abs(左子树-右子树)<1;

2. 求每个节点的高度(最深子树): Math.max(left,right);

ps:看了题解,遍历时使用后序遍历要更好，但我不知道我这个后序对不对(提交时间反而多了1ms)

public class Solution {
    /*
    判断是不是平衡二叉树：
    每个节点的左右子树高度差不超过1
      1.前序遍历每一个节点，每个节点都要满足:Math.abs(左子树-右子树)<1
      >>改进：使用后序遍历，先对底部的子树进行判断，可以减少对上层的遍历
      
      2.求每个节点的高度(最深子树)：Math.max(left,right);
    */
    public boolean IsBalanced_Solution(TreeNode root) {
        //使用后序遍历，先对子树进行判断
        if(root==null){
            return true;
        }
        if(!IsBalanced_Solution(root.left)){
            return false;
        }
        if(!IsBalanced_Solution(root.right)){
            return false;
        }
        int left = dfs(root.left);  //调用dfs获得当前节点左子树高度
        int right = dfs(root.right); //当前节点 右子树高度
        if(Math.abs(left-right)>1){ //判断高度差,当前节点是否满足平衡二叉树
            return false;
        }else{
            return true;
        }
      
/*        //对每个结点进行前序遍历
        if(root==null){
            return true;
        }
        int left = dfs(root.left);  //调用dfs获得当前节点左子树高度
        int right = dfs(root.right); //当前节点 右子树高度
        if(Math.abs(left-right)>1){ //判断高度差,当前节点是否满足平衡二叉树
            return false;
        }
        //对左右子树也进行递归判断
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
 */
    }
    public int dfs(TreeNode node){
        if(node==null){  //遍历到了底部
            return 0;
        }
        int left = dfs(node.left)+1;  //当前节点左子树高度
        int right = dfs(node.right)+1; //当前节点右子树高度
        return Math.max(left,right);  //返回最大高度
    }
}