使用二叉树的递归套路来解决的问题

时间:2022-09-18 11:07:23

作者:Grey

原文地址:

博客园:使用二叉树的递归套路来解决的问题

CSDN:使用二叉树的递归套路来解决的问题

说明

二叉树的递归套路本质是二叉树的后序遍历,如果你需要你的左树给你一些信息,右树给你一些信息,然后整合得到当前节点的信息,就可以用二叉树的递归套路。

以下问题都可以使用二叉树递归套路来解决,时间复杂度O(N)(即:经历一次后续遍历的时间复杂度)

是否完全二叉树

什么是完全二叉树:每一层都是满的,或者即便不满,也是从左到右依次变满的

梳理一下一棵树是完全二叉树的可能性,对于一棵树的根节点 root:

  1. 如果左右树都是满二叉树,那么当前节点为根节点的树一定是完全二叉树。

  2. 如果左右树不都是满二叉树,但是左边满足满二叉树,右边是完全二叉树,且左右树的高度一致,此时当前节点为根节点的树也是完全二叉树。

  3. 如果左右节点不都是满二叉树,左树是完全二叉树,右树是满二叉树,且左树高度比右树高度大1,此时当前节点为根节点的树也是完全二叉树。

除了上述三种可能性,其他情况下 root 为根节点的树都不是完全二叉树。

根据上述可能性,我们可以确认当前节点需要左右树给自己汇报如下三个信息

  1. 左右树是否满二叉树

  2. 左右树是否完全二叉树

  3. 左右树的高度

有以上三个信息,就可以判断上述的三种可能性了。

完整代码如下

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. 平衡二叉树要么是一棵空树。

  2. 要么保证左右子树的高度之差不大于 1。

  3. 子树也必须是一颗平衡二叉树。

根据上述可能性,我们可以确认当前节点需要左右树给自己汇报如下三个信息

  1. 左右树是否为平衡二叉树

  2. 左右树的高度

有以上二个信息,就可以判断上述的三种可能性了。

完整代码如下:

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, 有下述三种情况:

  1. 如果当前节点左树右树都不为空,且左右树都是搜索二叉树,且当前节点值比左树最大值都大,比右树最小值要小,则以 root 为根节点的树是二叉搜索树。

  2. 如果左树为空,且右树是搜索二叉树,且当前节点值比右树最小值要小。

  3. 如果右树为空,且左树是搜索二叉树,且当前节点值比左树最大值要大。

  4. 如果左右树都是空,默认当前节点就是二叉搜索树

除此之外,以 root 为节点的二叉树都不是搜索二叉树。

根据上述可能性,我们可以确认当前节点需要左右树给自己汇报如下三个信息

  1. 左右树的最大值

  2. 左右树的最小值

  3. 左右树是否是搜索二叉树

有以上三个信息,就可以判断上述的四种可能性了。

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遍历。

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云