使用二叉树的递归套路来解决的问题
作者：Grey
原文地址：
说明
二叉树的递归套路本质是二叉树的后序遍历，如果你需要你的左树给你一些信息，右树给你一些信息，然后整合得到当前节点的信息，就可以用二叉树的递归套路。
以下问题都可以使用二叉树递归套路来解决，时间复杂度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遍历。
