子樹

image.png

平衡二叉樹

image.png

判斷是否為平衡二叉樹

• 在遍歷樹的每個結(jié)點的時候，調(diào)用函數(shù)TreeDepth得到它的左右子樹的深度。如果每個結(jié)點的左右子樹的深度相差不超過1，按照定義它就是一棵平衡的二叉樹。顯然，我們會因此遍歷多次二叉樹，因此不推薦這種方法。

    /**
     * ★缺點：該方法在求該結(jié)點的的左右子樹深度時遍歷一遍樹，
     *         再次判斷子樹的平衡性時又遍歷一遍樹結(jié)構(gòu)，造成遍歷多次。
     * ★不推薦
     * @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;
    }

• 如果我們用后序遍歷的方式遍歷二叉樹的每個結(jié)點，在遍歷一個結(jié)點之前我們就已經(jīng)遍歷了它的左右子樹。只要在遍歷每個結(jié)點的時候我們記錄它的深度（某一節(jié)點的深度等于它到葉結(jié)點的路徑的長度），我們就可以一邊遍歷一邊判斷每個結(jié)點是不是平衡二叉樹。

    /**
     * 為了在一次遍歷中判斷二叉樹的平衡性，采用后序遍歷是一個不錯的想法。
     * @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;
    }