剑指Offer-平衡二叉树

发表于 | 阅读次数 | 阅读数

平衡二叉树

题目

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

思路

算每一个子是不是平衡二叉树

代码

public class IsBalanced_Solution {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    //算每个节点是否平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root==null){
            return true;
        }

        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        int diff = left -right;
        if (diff<-1||diff>1){
            return false;
        }

        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);

    }

    public int TreeDepth(TreeNode root){

        if (root==null){
            return 0;
        }

        if (root.left==null&&root.right==null){
            return 1;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);

        return left>right?left+1:right+1;
    }

    private boolean isBalnced= true;
    public Boolean IsBalanced_Solution_II(TreeNode root){
        check(root);
        return isBalnced;
    }

    private int  check(TreeNode root) {
        if (root==null) return 0;
        int left = check(root.left);
        int right = check(root.right);
        if (Math.abs(left-right)>1){
            isBalnced = false;
        }

        return right>left?right+1:left+1;
    }
}
0%