Java判断二叉树是否为平衡二叉树

题目描述

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

首先，平衡二叉树的定义：/*平衡二叉搜索树（Balanced Binary Tree）具有以下性质：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树*/

所以我想到的是递归的方法，判断左右的高度差，但是代码通过率只有28.57%

/*平衡二叉搜索树（Balanced Binary Tree）具有以下性质：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树*/
import java.util.*;

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }

        int left=0,right=0;

        if(root.left!=null&&IsBalanced_Solution(root.left)){
        left++;}

        if(root.right!=null&&IsBalanced_Solution(root.right)){
        right++;}



        if(left==right||left==right+1||right==left+1){
            return true;
        }
        return false;


    }
}

代码错在判断高度差的地方，每次递归会new一次int，但是这个int值没有被传出来，不能++，所以无论怎么递归，最后left和right的值都是1.

把这个判断高度的代码重新写一个depth()函数：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
       
        int left=depth(root.left);
        int right=depth(root.right);
        if(Math.abs(left-right)>1)
            return false;
         
        boolean booleft=IsBalanced_Solution(root.left);
        boolean booright=IsBalanced_Solution(root.right);
        return booleft&&booright;
    }
 
    public int depth(TreeNode root){
        if(root==null)
            return 0;
        int left=depth(root.left);
        int right=depth(root.right);
        return (left>right)?(left+1):(right+1);
    }
}

学习一下大神的解法：用后续遍历的方法

所谓后续遍历，就是先遍历左子树再遍历右子树，再遍历根节点。

跟上面的代码，思维差不多，但是因为用了一个全局的boolean，减少了子函数的判断步骤。

public class Solution {
    //后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
     
    private boolean isBalanced=true;
    public boolean IsBalanced_Solution(TreeNode root) {
         
        getDepth(root);
        return isBalanced;
    }
    public int getDepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getDepth(root.left);
        int right=getDepth(root.right);
         
        if(Math.abs(left-right)>1){
            isBalanced=false;
        }
        return right>left ?right+1:left+1;
         
    }
}