使用二元樹的遞迴套路來解決的問題

作者：Grey

原文地址：

部落格園：使用二元樹的遞迴套路來解決的問題

CSDN：使用二元樹的遞迴套路來解決的問題

說明

二元樹的遞迴套路本質是二元樹的後序遍歷，如果你需要你的左樹給你一些資訊，右樹給你一些資訊，然後整合得到當前節點的資訊，就可以用二元樹的遞迴套路。

以下問題都可以使用二元樹遞迴套路來解決，時間複雜度O(N)（即：經歷一次後續遍歷的時間複雜度）

是否完全二元樹

什麼是完全二元樹：每一層都是滿的，或者即便不滿，也是從左到右依次變滿的

梳理一下一棵樹是完全二元樹的可能性，對於一棵樹的根節點 root：

如果左右樹都是滿二元樹，那麼當前節點為根節點的樹一定是完全二元樹。
如果左右樹不都是滿二元樹，但是左邊滿足滿二元樹，右邊是完全二元樹，且左右樹的高度一致，此時當前節點為根節點的樹也是完全二元樹。
如果左右節點不都是滿二元樹，左樹是完全二元樹，右樹是滿二元樹，且左樹高度比右樹高度大1，此時當前節點為根節點的樹也是完全二元樹。

除了上述三種可能性，其他情況下 root 為根節點的樹都不是完全二元樹。

根據上述可能性，我們可以確認當前節點需要左右樹給自己彙報如下三個資訊。

左右樹是否滿二元樹
左右樹是否完全二元樹
左右樹的高度

有以上三個資訊，就可以判斷上述的三種可能性了。

完整程式碼如下

class Solution {
    public static class Info {
        // 是否滿二元樹
        private boolean isFull;
        // 是否完全二元樹
        private boolean isCBT;
        // 樹的高度
        private int height;

        public Info(boolean isFull, boolean isCBT, int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }
   public static boolean isCompleteTree(TreeNode head) {
        if (null == head) {
            return true;
        }
        return p(head).isCBT;
    }

    private static Info p(TreeNode head) {
        if (head == null) {
            return new Info(true, true, 0);
        }
        Info left = p(head.left);
        Info right = p(head.right);
        int height = Math.max(left.height, right.height) + 1;
        boolean isFull = left.isFull && right.isFull && (left.height == right.height);
        if (isFull) {
            // 是滿二元樹，肯定是完全二元樹
            return new Info(true, true, height);
        }
        // 不是滿二元樹
        if (left.height == right.height) {
            boolean isCBT = left.isFull && right.isCBT;
            return new Info(false, isCBT, height);
        }
        if (left.height - right.height == 1) {
            boolean isCBT = left.isCBT && right.isFull;
            return new Info(false, isCBT, height);
        }
        return new Info(false, false, height);
    }


}

是否為平衡二元樹

如何判斷一棵樹是否是平衡二元樹？有下述三種情況：

平衡二元樹要麼是一棵空樹。
要麼保證左右子樹的高度之差不大於 1。
子樹也必須是一顆平衡二元樹。

根據上述可能性，我們可以確認當前節點需要左右樹給自己彙報如下三個資訊。

左右樹是否為平衡二元樹
左右樹的高度

有以上二個資訊，就可以判斷上述的三種可能性了。

完整程式碼如下：

class Solution {
    public static boolean isBalanced(TreeNode head) {
        if (null == head) {
            return true;
        }
        return p(head).isBalanced;
    }

    private static Info p(TreeNode head) {
        if (head == null) {
            return new Info(0, true);
        }
        Info left = p(head.left);
        Info right = p(head.right);
        int height = Math.max(left.height, right.height) + 1;
        boolean isBalanced = (Math.abs(left.height - right.height) <= 1) && left.isBalanced && right.isBalanced;
        return new Info(height, isBalanced);
    }

    public static class Info {
        private int height;
        private boolean isBalanced;

        public Info(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }
}

是否為搜尋二元樹

如何判斷是否為二元搜尋樹？即：中序遍歷嚴格遞增。

對於一棵樹的根節點 root，有下述三種情況：

如果當前節點左樹右樹都不為空，且左右樹都是搜尋二元樹，且當前節點值比左樹最大值都大，比右樹最小值要小，則以 root 為根節點的樹是二元搜尋樹。
如果左樹為空，且右樹是搜尋二元樹，且當前節點值比右樹最小值要小。
如果右樹為空，且左樹是搜尋二元樹，且當前節點值比左樹最大值要大。
如果左右樹都是空，預設當前節點就是二元搜尋樹

除此之外，以 root 為節點的二元樹都不是搜尋二元樹。

根據上述可能性，我們可以確認當前節點需要左右樹給自己彙報如下三個資訊。

左右樹的最大值
左右樹的最小值
左右樹是否是搜尋二元樹

有以上三個資訊，就可以判斷上述的四種可能性了。

class Solution {
    public static class Info {
        public Info(int max, int min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
        // 最大值
        private int max;
        // 最小值
        private int min;
        // 是否是搜尋二元樹
        private boolean isBST;

    }
   public static boolean isValidBST(TreeNode head) {
        if (null == head) {
            return true;
        }
        return p(head).isBST;
    }

    public static Info p(TreeNode head) {
        if (head == null) {
            return null;
        }
        Info left = p(head.left);
        Info right = p(head.right);
        if (left == null && right == null) {
            return new Info(head.val, head.val, true);
        }

        if (left == null) {
            // right != null
            return new Info(Math.max(head.val, right.max), Math.min(head.val, right.min), right.isBST && head.val < right.min);
        }
        if (right == null) {
            // left != null
            return new Info(Math.max(head.val, left.max), Math.min(head.val, left.min), left.isBST && head.val > left.max);
        }
        return new Info(Math.max(head.val, Math.max(left.max, right.max)), Math.min(head.val, Math.min(left.min, right.min)), left.isBST && right.isBST && head.val < right.min && head.val > left.max);

    }



}

更多地，本題的最優解是 Morris 遍歷，可以在滿足時間複雜度O(N)的情況下，空間複雜度達到O(1)。

關於 Morris 遍歷的說明見:二元樹的先，中，後序遍歷(遞迴，非遞迴，Morris方法)

完整程式碼如下

class Solution {
     // Morris遍歷，O(1)空間複雜度
    public static boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean ans = true;
        TreeNode pre = null;
        TreeNode mostRight;
        TreeNode cur = root;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    if (pre != null && pre.val >= cur.val) {
                        ans = false;
                    }
                    pre = cur;
                    mostRight.right = null;
                }
            } else {
                if (pre != null && pre.val >= cur.val) {
                    ans = false;
                }
                pre = cur;
            }
            cur = cur.right;
        }
        return ans;
    }

}

什麼時候用二元樹的遞迴套路，什麼時候用 Morris 遍歷

如果你需要你的左樹給你一些資訊，右樹給你一些資訊，然後整合，這個時候就用二元樹的遞迴套路。

如果你用完左樹資訊後，可以不用再管左樹的資訊了，那麼就可以用Morris遍歷。

演演算法和資料結構筆記

參考資料

演演算法和資料結構體系班-左程雲