算法拾遗十七之二叉树的基本算法+二叉树的递归套路

二叉树折纸问题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。 例如:N=1时，打印: down N=2时，打印: down down up
思路：
我们把down看作凹下去的折痕，把up看作凸起来的折痕
每次有新的折痕都看作是在上一次新增的基础上前面加一个凹折痕，以及在后面加一个凸折痕。
那么就可以推出N=3的时候打印，down down up down down up up，也可以看作是二叉树的中序遍历，每次遍历的时候在叶子节点上面加一个左孩子和一个右孩子。
我们可以明确一条规律为：

根节点是凹的，每个左子树的头都是凹节点，每个右子树的头都是凸的。
那么建树的过程可以这样来建立【假设有三层】：
从上到下依次建立三个凹节点，接下来第三层再建立第四个凹节点的时候发现超出层数限制返回到第三个凹节点，打印自己第三个凹节点

然后判断第三个凹节点是否存在右子树：发现超出层数限制了，就不打印。

然后回到第二个节点打印一个凹节点，然后再走第二个节点的右子树，想象有一个凸节点，然后再
从右边的凸节点向下建立左边的凹节点，发现层数超限，返回输出那个凸节点，再从这个凸节点向右边去找它的凸节点，发现层数超限，返回到节点1，然后节点1再去建立它右边的凸节点，以此类推来得到最终的结果。

	public static void printAllFolds(int N) {
		//从第一层开始，折N次，然后开始节点为凹
		process(1, N, true);
		System.out.println();
	}

	// 当前你来了一个节点，脑海中想象的！
	// 这个节点在第i层，一共有N层，N固定不变的
	// 这个节点如果是凹的话，down = T
	// 这个节点如果是凸的话，down = F
	// 函数的功能：中序打印以你想象的节点为头的整棵树！
	public static void process(int i, int N, boolean down) {
		if (i > N) {
			return;
		}
		//我的左树
		process(i + 1, N, true);
		System.out.print(down ? "凹 " : "凸 ");
		//我的右树
		process(i + 1, N, false);
	}

	public static void main(String[] args) {
		int N = 4;
		printAllFolds(N);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

空间占用是O(N),节点数是2^N-1

判断是否是完全二叉树

1、如果一棵树有右孩子没有左孩子则不是完全二叉树
2、当第一次遇到左右孩子不双全的时候，剩下遍历的节点必须是叶子节点

  public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static boolean isCBT1(Node head) {
        if (head == null) {
            return true;
        }
        //二叉树按层遍历
        LinkedList<Node> queue = new LinkedList<>();
        // 是否遇到过左右两个孩子不双全的节点
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
                    (leaf && (l != null || r != null))
                            ||
                            (l == null && r != null)

            ) {
                //
                //如果右孩子不为空，左孩子为空返回false
                return false;
            }
            if (l != null) {
                queue.add(l);
            }
            if (r != null) {
                queue.add(r);
            }
            if (l == null || r == null) {
                //左右孩子如果有一个为空，那么剩下的节点必为叶子节点
                leaf = true;
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

判断一棵树是否是平衡二叉树[二叉树递归套路]

每一颗子树的高度差不超过1，只要有任何一颗子树不是平衡二叉树那么整棵树都不是平衡二叉树
给定一个头节点需满足：
1、x的左树是平衡二叉树
2、x的右树是平衡二叉树
3、x的左树高度减去x的右树高度的绝对值差值小于2
则需要收集每个子树是否是平衡二叉树，以及每个子树的高度是多少

	public static class Info{
		public boolean isBalanced;
		public int height;
		
		public Info(boolean i, int h) {
			isBalanced = i;
			height = h;
		}
	}
		public static boolean isBalanced2(Node head) {
		return process(head).isBalanced;
	}
	
	public static Info process(Node x) {
		if(x == null) {
			return new Info(true, 0);
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		int height = Math.max(leftInfo.height, rightInfo.height)  + 1;
		boolean isBalanced = true;
		if(!leftInfo.isBalanced) {
			isBalanced = false;
		}
		if(!rightInfo.isBalanced) {
			isBalanced = false;
		}
		if(Math.abs(leftInfo.height - rightInfo.height) > 1) {
			isBalanced = false;
		}
		return new Info(isBalanced, height);
	}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

判断一棵树是否是搜索二叉树【二叉树递归套路】

左子树每个值小于根节点，右子树每个值大于根节点
给定一个头节点X：
1、列出可能性，左树和右树的各种可能性
2、X的左树是搜索二叉树
3、X的右树是搜索二叉树
4、X的左树的最大值小于X
5、X的右树的最小值大于X
由于左右树条件不一样，需要提全集，就是说对于每棵树我既要最小值也要最大值【所有节点信息一次性全拿到】

  public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static boolean isBST(Node head) {
        if(head == null) {
            return true;
        }
        return process(head).isBST;
    }

    public static Info process(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        //生成三个信息,设置最大值和最小值为当前的value，分别与左树的最大和左树的最小比较
        int max = x.value;
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
        }

        int min = x.value;
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = true;
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        if (leftInfo != null && leftInfo.max >= x.value) {
            isBST = false;
        }
        if(rightInfo != null && rightInfo.min<=x.value) {
            isBST = false;
        }
        return new Info(isBST,max,min);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

判断一棵树是否是满二叉树

首先我们知道满二叉树的特点是节点数等于高度乘以2减去1

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	// 第一种方法
	// 收集整棵树的高度h，和节点数n
	// 只有满二叉树满足 : 2 ^ h - 1 == n
	public static boolean isFull1(Node head) {
		if (head == null) {
			return true;
		}
		Info1 all = process1(head);
		return (1 << all.height) - 1 == all.nodes;
	}

	public static class Info1 {
		public int height;
		public int nodes;

		public Info1(int h, int n) {
			height = h;
			nodes = n;
		}
	}

	public static Info1 process1(Node head) {
		if (head == null) {
			return new Info1(0, 0);
		}
		Info1 leftInfo = process1(head.left);
		Info1 rightInfo = process1(head.right);
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		int nodes = leftInfo.nodes + rightInfo.nodes + 1;
		return new Info1(height, nodes);
	}

	// 第二种方法
	// 收集子树是否是满二叉树
	// 收集子树的高度
	// 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的
	public static boolean isFull2(Node head) {
		if (head == null) {
			return true;
		}
		return process2(head).isFull;
	}

	public static class Info2 {
		public boolean isFull;
		public int height;

		public Info2(boolean f, int h) {
			isFull = f;
			height = h;
		}
	}

	public static Info2 process2(Node h) {
		if (h == null) {
			return new Info2(true, 0);
		}
		Info2 leftInfo = process2(h.left);
		Info2 rightInfo = process2(h.right);
		boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		return new Info2(isFull, height);
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

二叉树递归套路实践

给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离【距离
就是指一棵树上一个节点到另一个节点最短的距离】。

如上从右子树下面的一个节点到另一个节点，距离为4。
首先目标是求以X为头的树的最大距离
列可能性：
1、是否与X有关【求距离是否通过X节点】-》可通过也可以不通过
1-1、X无关（X左树上的最大距离，或者X右树上的最大距离）
1-2、X有关（路径经过X）【X左树最远的点【左树高度】和X右树最远的点【右树高度】构成最大距离】最后在加个
X本身的1

  public static int maxDistance(Node head) {
        return process(head).maxDistance;
    }

    public static class Info {
        public int maxDistance;
        public int height;

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

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(Math.max(p1, p2), p3);
        return new Info(maxDistance, height);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

二叉树递归套路实现二

整棵树不是搜索二叉树，但它有子树【叶子节点，根节点构成树，以及下图圈起来的部分】是搜索二叉树，在所有子树里面找最大的搜索二叉树，并返回所有节点

如上图应该返回4。
首先确定目标，是求以X为头节点书上的BST子树的maxSize
可能性：
1、x不做头，比较左子树上的最大二叉搜索树的size与右子树上的最大二叉搜索树
的size
2、x做头，x整体都是二叉搜索树才成立【判定左树是否是搜索二叉树，
右树是否是搜索二叉树，左树的最大值小于X，右树的最小值大于X，
，以及知道左树的size大小和右树的size大小，加个1得到答案】
如上归纳为以下信息：
1、maxBSTSubSize 最大搜索二叉树大小
2、isBST 是否是平衡二叉树
3、max 整棵树的最大值
4、min 整棵树的最小值
5、size 整棵树的大小
注意：
如果size = maxBSTSubSize 则代表整棵树是搜索二叉树，就可以省略isBST变量

    public static int maxSubBSTSize(TreeNode head) {
        if(head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    public static class Info {
        public int maxBSTSubtreeSize;
        public int allSize;
        public int max;
        public int min;

        public Info(int maxBSTSubtreeSize, int allSize, int max, int min) {
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.allSize = allSize;
            this.max = max;
            this.min = min;
        }
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int max = x.val;
        int min = x.val;
        int allSize = 1;
        int maxBSTSubtreeSize;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        //单独x左树上的二叉搜索树大小
        int p1 = -1;
        if (leftInfo != null) {
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        //单独x右树上的二叉树大小
        int p2 = -1;
        if (rightInfo != null) {
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        //包含x及左右树
        int p3 = -1;
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        if (leftBST && rightBST) {
            //左树的最大小于X
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
            //右树的最小值是否大于X
            boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
            if (leftMaxLessX && rightMinMoreX) {
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
            }
        }
        return new Info(Math.max(p1,Math.max(p2,p3)),allSize,max,min);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

二叉树递归套路总结

刚才的方法时间复杂度为O(N)，根据前面文章的递归序，
假如说我的info里面有三个信息

我叶子节点的左子树下面是空，我拿到三个信息，我叶子节点的右子树是空，我也能拿到三个信息，然后
把左边和右边拿到的三个信息向上整合成我的叶子节点的三个信息，然后将这个信息给我的父节点。
整个过程类似于一个后续遍历（左树加工三个信息，右树加工三个信息），所以叫树型DP
这个套路包含两个层次：
1、对思想上的极大提醒【以X为头目标怎么实现】
2、写代码的时候模板化

总体

1）假设以X节点为头，假设可以向X左树和X右树要任何信息
2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
5）递归函数都返回S，每一棵子树都这么要求
6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息