子树

image.png

平衡二叉树

image.png

判断是否为平衡二叉树

• 在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差不超过1，按照定义它就是一棵平衡的二叉树。显然，我们会因此遍历多次二叉树，因此不推荐这种方法。

    /**
     * ★缺点：该方法在求该结点的的左右子树深度时遍历一遍树，
     *         再次判断子树的平衡性时又遍历一遍树结构，造成遍历多次。
     * ★不推荐
     * @param head
     * @return
     */
    public static boolean isBalanceRecursive(Node head){
        if (head == null)
            return true;

        int nleft = treeDepth(head.left);
        int nright = treeDepth(head.right);
        int differ = nleft - nright;

        if(differ > 1 || differ < -1)
            return false;

        return isBalanceRecursive(head.left) && isBalanceRecursive(head.right);
    }

    public static int treeDepth(Node head){
        if (head == null)
            return 0;

        int leftDepth = treeDepth(head.left);
        int rightDepth = treeDepth(head.right);

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

• 如果我们用后序遍历的方式遍历二叉树的每个结点，在遍历一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候我们记录它的深度（某一节点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡二叉树。

    /**
     * 为了在一次遍历中判断二叉树的平衡性，采用后序遍历是一个不错的想法。
     * @param head
     * @return
     */
    public static boolean isBalance(Node head){
        return isBalance(head, 0);
    }

    public static boolean isBalance(Node head, int depth){
        if(head == null){
            depth = 0;
            return true;
        }

        int left = 0, right = 0;
        if (isBalance(head.left, left) && isBalance(head.right, right)){
            int diff = left - right;
            if(diff <= 1 && diff >= -1){
                depth = left > right ? left + 1 : right + 1;
                return true;
            }
        }
        
        return false;
    }