ShiYu

# 第12节 二叉树的基本算法+二叉树的递归套路

# 二叉树的递归套路深度实践一

判断二叉树是否是完全二叉树

会在后面的题目中用二叉树的递归套路来解这个题

非递归套路之解题思路：

  • 定义叶子节点开关isleaf=false

  • 按层遍历节点若存在孩子不双全则isleaf=true判断节点若是有右无左并且叶子节点开关开启时节点必须是叶子节点

递归套路之解题思路：

  • 以X节点为头的二叉树判断二叉树是否是完全二叉树
  • 列出可能性
    • 左树高度与右数高度时 左树必须是满二叉树 右树是完全二叉树或者满二叉树
    • 左树高度==右数高度+1 左树是完全二叉树或者满二叉树 右树必须是满二叉树
  • 向左、右两子树要信息(可能性求全集)
    • 树的高度
    • 是否是完全二叉树
    • 是否是满二叉树

代码：

package class12;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 	判断二叉树是否是完全二叉树
 * @author yangyanchao
 *
 */
public class Test01_IsCBT {
	
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	判断二叉树是否是完全二叉树-非递归版本
	 * @param head
	 * @return
	 */
	public static boolean isCBTUnRecursive(TreeNode head) {
		if(head == null) {
			return true;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(head);
		boolean isleaf = false;
		TreeNode cur = null;
		TreeNode l = null;
		TreeNode r = null;
		// 按层遍历
		while(!queue.isEmpty()) {
			cur = queue.poll();
			l = cur.left;
			r = cur.right;
			if((l == null && r != null) || (isleaf && (l != null || r != null))) {
				return false;
			}
			if(l == null || r == null) {
				isleaf = true;
			}
			if(l != null) {
				queue.add(l);
			}
			if(r != null) {
				queue.add(r);
			}
		}
		return true;
		
	}
	
	/**
	 * 	判断二叉树是否是完全二叉树-递归版本 使用递归套路
	 * @param head
	 * @return
	 */
	public static boolean isCBTRecursive(TreeNode head) {
		if(head == null) {
			return true;
		}
		return process(head).isCBT;
	}
	
	/**
	 * 	递归套路信息类
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public boolean isFBT;// 是否是满二叉树
		public boolean isCBT;// 是否是完全二叉树
		public int height;   // 树的高度
		public Info(boolean isFBT, boolean isCBT, int height) {
			this.isFBT = isFBT;
			this.isCBT = isCBT;
			this.height = height;
		}
	}
	
	public static Info process(TreeNode x) {
		if(x == null) {
			return new Info(true, true, 0);
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
		boolean isFBT = leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height;
		boolean isCBT = false;
		if(isFBT) {
			isCBT = true;
		} else if(leftInfo.isCBT && rightInfo.isCBT){
			
			int cha = leftInfo.height - rightInfo.height;
			if(cha == 0 && (leftInfo.isFBT && (rightInfo.isCBT || rightInfo.isFBT))) {
				// 左右树高度一致
				isCBT = true;
			} else if(cha == 1 && ((leftInfo.isCBT || leftInfo.isFBT) && rightInfo.isFBT)){
				// 左比右树高度高1
				isCBT = true;
			}
		}
		return new Info(isFBT, isCBT, height);
	}
	
	public static void main(String[] args) {
		int maxLevel = 10;
		int maxValue = 100;
		int testTimes = 100000;
		boolean succed = true;
		for(int i = 0; i < testTimes; i++) {
			TreeNode node = generateRandomTreeNode(maxLevel, maxValue);
			boolean res1 = isCBTUnRecursive(node);
			boolean res2 = isCBTRecursive(node);
			if(res1 != res2) {
				System.out.println("res1: " + res1);
				System.out.println("res2: " + res2);
				succed = false;
				break;
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo");
	}

	/**
	 * 	随机生成二叉树节点信息
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateTreeNodeProcess(1, maxLevel, maxValue);
	}

	/**
	 * 	递归函数
	 * @param i
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateTreeNodeProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)Math.random() * maxValue);
		head.left = generateTreeNodeProcess(i + 1, maxLevel, maxValue);
		head.right = generateTreeNodeProcess(i + 1, maxLevel, maxValue);
		return head;
	}
	
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

# 二叉树的递归套路深度实践二

判断二叉树是否是搜索二叉树

  • 搜索二叉树：二叉树的左树的最大值比头节点小并且右树的最小值比头节点大

非递归之解题思路：

  • 二叉树中序遍历的结果是升序的

递归套路之解题思路：

  • 以X节点为头的二叉树判断二叉树是否是搜索二叉树
  • 列出可能性
    • 是否是搜索二叉树isBST
    • 左树的最大值max
    • 右树的最小值min
  • 向左、右两子树要信息(可能性求全集)
    • 是否是搜索二叉树isBST
    • 最大值max
    • 最小值min

代码：

package class12;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 	判断二叉树是否是搜索二叉树
 * @author yangyanchao
 *
 */
public class Test02_IsBST {
	
	/**
	 * 	二叉树节点
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	判断二叉树是否是搜索二叉树-非递归版本
	 * 	中序遍历使用递归序
	 * @param head
	 * @return
	 */
	public static boolean isBSTUnRecursive(TreeNode head) {
		if(head == null) {
			return true;
		}
		ArrayList<TreeNode> list = new ArrayList<>();
		in(head, list);
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i).value <= list.get(i - 1).value) {
				return false;
			}
		}
		return true;
	}
	
	private static void in(TreeNode head, ArrayList<TreeNode> list) {
		if(head == null) {
			return ;
		}
		in(head.left, list);
		list.add(head);
		in(head.right, list);
	}

	/**
	 * 	判断二叉树是否是搜索二叉树-非递归版本
	 * 	中序遍历使用栈
	 * @param head
	 * @return
	 */
	public static boolean isBSTUnRecursiveStack(TreeNode head) {
		if(head == null) {
			return true;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = head;
		ArrayList<TreeNode> list = new ArrayList<>();
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.pop();
				list.add(cur);
				cur = cur.right;
			}
		}
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i).value <= list.get(i - 1).value) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 	判断二叉树是否是搜索二叉树-递归版本
	 * @param head
	 * @return
	 */
	public static boolean isBSTRecursive(TreeNode head) {
		if(head == null) {
			return true;
		}
		return process(head).isBST;
		
	}
	
	/**
	 * 	套路中的信息体
	 * @author yangyanchao
	 *
	 */
	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;
		}
	}
	
	/**
	 * 	递归过程
	 * 	以x节点为头，判断是否是搜索二叉树
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode x) {
		if(x == null) {
			return null;
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		int max = x.value;
		int min = x.value;
		if(leftInfo != null) {
			max = Math.max(max, leftInfo.max);
			min = Math.min(min, leftInfo.min);
		}
		if(rightInfo != null) {
			max = Math.max(max, rightInfo.max);
			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);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		TreeNode node = null;
		boolean flag1 = false;
		boolean flag2 = false;
		boolean flag3 = false;
		boolean succed = true;
		for(int i = 0; i < maxTestTimes; i++) {
			node = generateRandomTreeNode(maxLevel, maxValue);
			flag1 = isBSTUnRecursive(node);
			flag2 = isBSTRecursive(node);
			flag3 = isBSTUnRecursiveStack(node);
			if(flag1 != flag3 && flag1 != flag2) {
				succed = false;
				System.out.println(flag1 + "  " + flag2 + "  " + flag3);
				break;
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo" );
	}

	/**
	 * 	随机生成二叉树
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	/**
	 * 	递归生成
	 * @param head
	 * @param i
	 * @param maxLevel
	 * @param maxValue
	 */
	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}

	
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

# 二叉树的递归套路深度实践三

给定一棵二叉树的头节点head，返回这颗二叉树是不是平衡二叉树

  • 平衡二叉树：左树高度与右树高度相差的绝对值不超过1(<=1)

非递归套路之解题思路：

  • 传递标识，初始为true，判断左树高度与右树高度相差的绝对值超过1则为false
  • 递归过程返回数的最大高度

递归套路之解题思路：

  • 以X节点为头的二叉树判断二叉树是否是平衡二叉树
  • 列出可能性
    • 是否是平衡二叉树IsBalanced
    • 左树高度
    • 右树高度
  • 向左、右两子树要信息(可能性求全集)
    • 是否是平衡二叉树IsBalanced
    • 高度height

代码：

package class12;

/**
 * 	判断二叉树是否是平衡二叉树
 * @author yangyanchao
 *
 */
public class Test03_IsBalanced {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	判断二叉树是否是平衡二叉树--非递归套路版本
	 * @param head
	 * @return
	 */
	public static boolean isBalancedUnRecursiveTricks(TreeNode head) {
		boolean[] ans = new boolean[1];
		ans[0] = true;
		process(head, ans);
		return ans[0];
	}
	
	/**
	 * 	递归过程
	 * @param head
	 * @param ans
	 * @return
	 */
	private static int process(TreeNode head, boolean[] ans) {
		if(!ans[0] || head == null) {
			return -1;
		}
		int leftHeight = process(head.left, ans);
		int rightHeight = process(head.right, ans);
		if(Math.abs(leftHeight - rightHeight) > 1) {
			ans[0] = false;
		}
		return Math.max(leftHeight, rightHeight) + 1;
	}

	/**
	 * 	判断二叉树是否是平衡二叉树--递归套路版本
	 * @param head
	 * @return
	 */
	public static boolean isBalancedRecursiveTricks(TreeNode head) {
		return process(head).isBalanced;
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public boolean isBalanced;
		public int height;
		public Info(boolean isBalanced, int height) {
			this.isBalanced = isBalanced;
			this.height = height;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode 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 = false;
		if(leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height-rightInfo.height) < 2) {
			isBalanced = true;
		}
		return new Info(isBalanced, height);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		TreeNode node = null;
		boolean flag1 = false;
		boolean flag2 = true;
		boolean succed = true;
		for(int i = 0; i < maxTestTimes; i++) {
			node = generateRandomTreeNode(maxLevel, maxValue);
			flag1 = isBalancedUnRecursiveTricks(node);
			flag2 = isBalancedRecursiveTricks(node);
			if(flag1 != flag2) {
				succed = false;
				System.out.println(flag1 + "  " + flag2);
				break;
			}
		}
		
		System.out.println(succed ? "Nice" : "ooVoo" );
	}

	/**
	 * 	随机生成二叉树节点
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	/**
	 * 	递归生成
	 * @param i
	 * @param maxLevel
	 * @param maxValue
	 * @return
	 */
	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

# 二叉树的递归套路深度实践四

给定一棵二叉树的头节点head，返回这颗二叉树是否是满二叉树

  • 满二叉树：树的高度h及节点数量allSize的关系为(1<<h) - 1 == allSize(2的h次方-1)

非递归套路之解题思路：

  • 按层遍历记录高度与节点数量或者递归求出高度、节点数量
  • 然后判断树的高度h及节点数量allSize的关系为(1<<h) - 1 == allSize(2的h次方-1)

递归套路之解题思路：

  • 以X节点为头的二叉树判断二叉树是否是满二叉树
  • 列出可能性
    • 树高度
    • 树节点数量
  • 向左、右两子树要信息(可能性求全集)
    • 高度height
    • 节点数量allSize

代码：

package class12;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 	判断二叉树是否是满二叉树
 * @author yangyanchao
 *
 */
public class Test04_IsFull {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	判断二叉树是否是满二叉树--非递归套路版本
	 * 	层级遍历
	 * @param head
	 * @return
	 */
	public static boolean isFullUnRecursiveTricks(TreeNode head) {
		if (head == null) {
			return true;
		}
		int height = 0;
		int allSize = 0;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(head);
		TreeNode curLevelEnd = head;
		TreeNode nextLevelEnd = head;
		while(!queue.isEmpty()) {
			head = queue.poll();
			allSize++;
			if(head.left != null) {
				queue.add(head.left);
				nextLevelEnd = head.left;
			}
			if(head.right != null) {
				queue.add(head.right);
				nextLevelEnd = head.right;
			}
			if(curLevelEnd == head) {
				height++;
				curLevelEnd = nextLevelEnd;
			}
		}
		return (1 << height) - 1 == allSize;
	}
	
	/**
	 * 	判断二叉树是否是满二叉树--非递归套路版本
	 * @param head
	 * @return
	 */
	public static boolean isFullUnRecursiveTricks1(TreeNode head) {
		if (head == null) {
			return true;
		}
		int height = processHeight(head);
		int allSize = processSize(head);
		return (1 << height) - 1 == allSize;
	}
	
	private static int processSize(TreeNode head) {
		if(head == null) {
			return 0;
		}
		return processSize(head.left) + processSize(head.right) + 1;
	}

	private static int processHeight(TreeNode head) {
		if(head == null) {
			return 0;
		}
		return Math.max(processHeight(head.left), processHeight(head.right)) + 1;
	}

	/**
	 * 	判断二叉树是否是满二叉树--递归套路版本
	 * @param head
	 * @return
	 */
	public static boolean isFullRecursiveTricks(TreeNode head) {
		if (head == null) {
			return true;
		}
		Info info = process(head);
		return (1 << info.height) - 1 == info.allSize;
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public int height;
		public int allSize;
		public Info(int height, int allSize) {
			this.height = height;
			this.allSize = allSize;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode 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 allSize = leftInfo.allSize + rightInfo.allSize + 1;
		return new Info(height, allSize);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		TreeNode node = null;
		boolean succed = true;
		boolean flag1 = false;
		boolean flag2 = false;
		boolean flag3 = false;
		for(int i = 0; i < maxTestTimes; i++) {
			node = generateRandomTreeNode(maxLevel, maxValue);
			flag1 = isFullUnRecursiveTricks1(node);
			flag2 = isFullRecursiveTricks(node);
			flag3 = isFullUnRecursiveTricks(node);
			if(flag1 != flag2 || flag1 != flag3) {
				succed = false;
				System.out.println(flag1 + " " + flag2 + " " + flag3);
				break;
			}
		}
		System.out.println(succed ? "Nice" : "ooVoo");
	}

	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

# 二叉树的递归套路深度实践五

给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的大小

非递归套路之解题思路：

  • 若是和头节点有关则中序遍历返回二叉搜索子树的大小
  • 若是无关则返回左树与右树的最大值

递归套路之解题思路：

  • 以X节点为头的二叉树返回二叉中最大的二叉搜索子树的大小
  • 列出可能性
    • 与X节点无关
      • 左树的最大搜索子树大小
      • 右树的最大搜索子树大小
    • 与X节点有关
      • 左树是否是二叉搜索树
      • 右树是否是二叉搜索树
      • 左树的最大值
      • 右树的最小值
      • 树的节点数量
  • 向左、右两子树要信息(可能性求全集)
    • 最大搜索子树大小maxSubBSTSize
    • 节点数量allSize
    • 最大值max
    • 最小值min

代码：

package class12;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 	返回二叉中最大的二叉搜索子树的大小
 * @author yangyanchao
 *
 */
public class Test05_MaxSubBSTSize {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	返回二叉树中最大的二叉搜索子树的大小--非递归套路版本
	 * 	采用中序遍历 使用栈
	 * @param head
	 * @return
	 */
	public static int maxSubBSTSizeUnRecursiveTricks1(TreeNode head) {
		return process2(head);
	}
	
	private static int process2(TreeNode x) {
		if(x == null) {
			return 0;
		}
		int size = getBSTSize2(x);
		if(size != 0) {
			// 与x节点有关返回它的节点数量
			return size;
		}
		// 与x节点无关
		return Math.max(process1(x.left), process1(x.right));
	}
	
	private static int getBSTSize2(TreeNode x) {
		ArrayList<TreeNode> list = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = x;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				cur = stack.pop();
				list.add(cur);
				cur = cur.right;
			}
		}
		
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i).value <= list.get(i - 1).value) {
				return 0;
			}
		}
		return list.size();
	}
	
	/**
	 * 	返回二叉树中最大的二叉搜索子树的大小--非递归套路版本
	 * 	采用中序遍历 递归序
	 * @param head
	 * @return
	 */
	public static int maxSubBSTSizeUnRecursiveTricks(TreeNode head) {
		return process1(head);
	}
	
	private static int process1(TreeNode x) {
		if(x == null) {
			return 0;
		}
		int size = getBSTSize1(x);
		if(size != 0) {
			// 与x节点有关返回它的节点数量
			return size;
		}
		// 与x节点无关
		return Math.max(process1(x.left), process1(x.right));
	}

	private static int getBSTSize1(TreeNode x) {
		ArrayList<TreeNode> list = new ArrayList<>();
		in(x, list);
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i).value <= list.get(i - 1).value) {
				return 0;
			}
		}
		return list.size();
	}

	private static void in(TreeNode x, ArrayList<TreeNode> list) {
		if(x == null) {
			return;
		}
		in(x.left, list);
		list.add(x);
		in(x.right, list);
	}

	/**
	 * 	返回二叉树中最大的二叉搜索子树的大小--递归套路版本
	 * @param head
	 * @return
	 */
	public static int maxSubBSTSizeRecursiveTricks(TreeNode head) {
		if(head == null) {
			return 0;
		}
		return process(head).maxSubBSTSize;
	}
	
	/**
	 * 	递归信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public int maxSubBSTSize;
		public int allSize;
		public int max;
		public int min;
		public Info(int maxSubBSTSize, int allSize, int max, int min) {
			this.maxSubBSTSize = maxSubBSTSize;
			this.allSize = allSize;
			this.max = max;
			this.min = min;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode x) {
		if(x == null) {
			return null;
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		int allSize = 1;
		int max = x.value;
		int min = x.value;
		if(leftInfo != null) {
			allSize += leftInfo.allSize;
			max = Math.max(leftInfo.max, max);
			min = Math.min(leftInfo.min, min);
		}
		if(rightInfo != null) {
			allSize += rightInfo.allSize;
			max = Math.max(rightInfo.max, max);
			min = Math.min(rightInfo.min, min);
		}
		int maxSubBSTSize = -1;
		boolean leftIsBST = leftInfo == null ? true : leftInfo.maxSubBSTSize == leftInfo.allSize ;
		boolean rightIsBST = rightInfo == null ? true : rightInfo.maxSubBSTSize == rightInfo.allSize ;
		if(leftIsBST && rightIsBST) {
			boolean leftMaxLess = leftInfo == null ? true : leftInfo.max < x.value;
			boolean rightMinMore = rightInfo == null ? true : rightInfo.min > x.value;
			if(leftMaxLess && rightMinMore) {
				maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.allSize) + 
						(rightInfo == null ? 0 : rightInfo.allSize) + 1;
			}
		}
		int leftMaxSubBSTSize = leftInfo == null ? 0 : leftInfo.maxSubBSTSize;
		int rightMaxSubBSTSize = rightInfo == null ? 0 : rightInfo.maxSubBSTSize;
		maxSubBSTSize = Math.max(Math.max(leftMaxSubBSTSize, rightMaxSubBSTSize), maxSubBSTSize);
		return new Info(maxSubBSTSize, allSize, max, min);
	}
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		boolean succed = true;
		int count1 = -1;
		int count2 = -1;
		int count3 = -1;
		for(int i = 0; i < maxTestTimes; i++) {
			TreeNode node = generateRandomTreeNode(maxLevel, maxValue);
			count1 = maxSubBSTSizeUnRecursiveTricks(node);
			count2 = maxSubBSTSizeRecursiveTricks(node);
			count3 = maxSubBSTSizeUnRecursiveTricks1(node);
			if(count1 != count2 || count1 != count3) {
				succed = false;
				System.out.println(count1 + "  " + count2 + "  " + count3);
				break;
			}
		}
		System.out.println(succed ? "Nice" : "ooVoo");
	}

	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

# 二叉树的递归套路深度实践六

给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离

递归套路之解题思路：

  • 以X节点为头的二叉树返回二叉树的最大距离
  • 列出可能性
    • 与X节点无关
      • 左树的最大距离
      • 右树的最大距离
    • 与X节点有关
      • 左树高度+右树高度+1
  • 向左、右两子树要信息(可能性求全集)
    • 高度height
    • 最大距离maxDistance

代码：

package class12;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 * 	返回二叉树中任意两节点的最大距离
 * @author yangyanchao
 *
 */
public class Test06_MaxDistance {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	返回二叉树中任意两节点的最大距离--非递归套路版本
	 * 	不使用递归
	 * @param head
	 * @return
	 */
	public static int maxDistanceUnRecursiveTricks1(TreeNode head) {
		if(head == null) {
			return 0;
		}
		// 返回列表记录每个节点
		List<TreeNode> list = transformListByTreeNode(head);
		// 记录各个节点的父亲节点
		Map<TreeNode, TreeNode> parentMap = transformMapByTreeNode(head);
		// 开始遍历 任意两节点的距离 计算出最大距离 
		// 查找两个节点距离思路是 
		// a节点的所有祖先节点入HashSet,b节点往上找祖先节点并比对HashSet中有无存在的节点若存在则找出最低公共祖先lowestAncestor
		// 然后再从a节点开始往上找到lowestAncestor记录距离a1,b节点往上找到lowestAncestor记录距离b1，最终距离为a1+b1-1
		int maxDistance = 0;
		for(int i = 0; i < list.size(); i++) {
			for(int j = i; j < list.size(); j++) {
				maxDistance = Math.max(maxDistance, distance(parentMap, list.get(i), list.get(j)));
			}
		}
		
		return maxDistance;
	}
	
	private static int distance(Map<TreeNode, TreeNode> parentMap, TreeNode a, TreeNode b) {
		TreeNode cur = a;
		HashSet<TreeNode> sets = new HashSet<>();
		while(cur != null) {
			sets.add(cur);
			cur = parentMap.get(cur);
		}
		cur = b;
		while(!sets.contains(cur)) {
			cur = parentMap.get(cur);
		}
		TreeNode lowestAncestor = cur;
		int a1 = 1;
		cur = a;
		while(cur != lowestAncestor) {
			cur = parentMap.get(cur);
			a1++;
		}
		int b1 = 1;
		cur = b;
		while(cur != lowestAncestor) {
			cur = parentMap.get(cur);
			b1++;
		}
		return a1 + b1 + 1;
	}

	private static List<TreeNode> transformListByTreeNode(TreeNode head) {
		List<TreeNode> list = new ArrayList<>();
		transformListProcess(head, list);
		return list;
	}

	private static void transformListProcess(TreeNode head, List<TreeNode> list) {
		if(head == null) {
			return;
		}
		list.add(head);
		transformListProcess(head.left, list);
		transformListProcess(head.right, list);
	}

	private static Map<TreeNode, TreeNode> transformMapByTreeNode(TreeNode head) {
		Map<TreeNode, TreeNode> parent = new HashMap<>();
		parent.put(head, null);
		transformMapProcess(head, parent);
		return parent;
	}

	private static void transformMapProcess(TreeNode head, Map<TreeNode, TreeNode> parent) {
		if(head.left != null) {
			parent.put(head.left, head);
			transformMapProcess(head.left, parent);
		}
		if(head.right != null) {
			parent.put(head.right, head);
			transformMapProcess(head.right, parent);
		}
	}

	/**
	 * 	返回二叉树中任意两节点的最大距离--非递归套路版本
	 * 	使用了递归
	 * @param head
	 * @return
	 */
	public static int maxDistanceUnRecursiveTricks(TreeNode head) {
		if(head == null) {
			return 0;
		}
		int[] maxDistance = new int[1];
		maxDistance[0] = 0;
		process1(head, maxDistance);
		return maxDistance[0];
	}
	
	private static int process1(TreeNode head, int[] maxDistance) {
		if(head == null) {
			return 0;
		}
		// 与head无关
		int leftHeight = process1(head.left, maxDistance);
		int rightHeight = process1(head.right, maxDistance);
		int height = Math.max(leftHeight, rightHeight) + 1;
		maxDistance[0] = Math.max(maxDistance[0], leftHeight + rightHeight + 1);
		return height;
	}

	/**
	 * 	返回二叉树中任意两节点的最大距离--递归套路版本
	 * @param head
	 * @return
	 */
	public static int maxDistanceRecursiveTricks(TreeNode head) {
		if(head == null) {
			return 0;
		}
		return process(head).maxDistance;
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	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(TreeNode 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);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		int distance1 = 0;
		int distance2 = 0;
		int distance3 = 0;
		boolean succed = true;
		for(int i = 0; i < maxTestTimes; i++) {
			TreeNode node = generateRandomTreeNode(maxLevel, maxValue);
			distance1 = maxDistanceUnRecursiveTricks(node);
			distance2 = maxDistanceRecursiveTricks(node);
			distance3 = maxDistanceUnRecursiveTricks1(node);
			if(distance1 != distance2 && distance1 != distance3) {
				succed = false;
				System.out.println(distance1 + "     " + distance2 + "     " + distance3);
				break;
			}
		}
		System.out.println(succed ? "Nice" : "ooVoo");
	}

	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

# 二叉树的递归套路深度实践七

给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点

非递归套路之解题思路：

  • 若是和头节点有关则中序遍历返回二叉搜索子树的大小
  • 若是无关则返回左树与右树的最大值

递归套路之解题思路：

  • 以X节点为头的二叉树返回二叉中最大的二叉搜索子树的头节点
  • 列出可能性
    • 与X节点无关
      • 左树的最大搜索子树的头节点
      • 左树的最大搜索子树的大小
      • 右树的最大搜索子树的头节点
      • 左树的最大搜索子树的大小
    • 与X节点有关
      • 左树是否是二叉搜索树
      • 右树是否是二叉搜索树
      • 左树的最大值
      • 右树的最小值
  • 向左、右两子树要信息(可能性求全集)
    • 最大搜索子树的头节点maxSubBSTHead
    • 最大搜索子树的大小maxSubBSTSize
    • 最大值max
    • 最小值min

代码：

package class12;

import java.util.ArrayList;
import java.util.List;

/**
 * 	给定一棵二叉树的头节点head，返回这颗二叉树中最大的二叉搜索子树的头节点
 * @author yangyanchao
 *
 */
public class Test07_MaxSubBSTHead {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	返回这颗二叉树中最大的二叉搜索子树的头节点--非递归套路版本
	 * @param head
	 * @return
	 */
	public static TreeNode maxSubBSTHeadUnRecursiveTricks(TreeNode head) {
		if(head == null) {
			return null;
		}
		if(getBSTSize(head) != 0) {
			return head;
		}
		TreeNode leftAns = maxSubBSTHeadUnRecursiveTricks(head.left);
		TreeNode rightAns = maxSubBSTHeadUnRecursiveTricks(head.right);
		return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
	}
	
	/**
	 * 	中序遍历 判断是否是升序的 是->是二叉搜索树 否->否
	 * @param head
	 * @return
	 */
	private static int getBSTSize(TreeNode head) {
		List<TreeNode> list = new ArrayList<>();
		in(head, list);
		for(int i = 1; i < list.size(); i++) {
			if(list.get(i).value <= list.get(i - 1).value) {
				return 0;
			}
		}
		return list.size();
	}

	private static void in(TreeNode head, List<TreeNode> list) {
		if(head == null) {
			return;
		}
		in(head.left, list);
		list.add(head);
		in(head.right, list);
	}

	/**
	 * 	返回这颗二叉树中最大的二叉搜索子树的头节点--递归套路版本
	 * @param head
	 * @return
	 */
	public static TreeNode maxSubBSTHeadRecursiveTricks(TreeNode head) {
		if(head == null || process(head) == null) {
			return null;
		}
		return process(head).maxSubBSTHead;
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public TreeNode maxSubBSTHead;
		public int maxSubBSTSize;
		public int max;
		public int min;
		public Info(TreeNode maxSubBSTHead, int maxSubBSTSize, int max, int min) {
			this.maxSubBSTHead = maxSubBSTHead;
			this.maxSubBSTSize = maxSubBSTSize;
			this.max = max;
			this.min = min;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode x) {
		if(x == null) {
			return null;
		}
		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);
		TreeNode maxSubBSTHead = null;
		int maxSubBSTSize = 0;
		int max = x.value;
		int min = x.value;
		// 与X节点无关
		if(leftInfo != null) {
			if(leftInfo.maxSubBSTSize > maxSubBSTSize) {
				maxSubBSTHead = leftInfo.maxSubBSTHead;
				maxSubBSTSize = leftInfo.maxSubBSTSize;
			}
			max = Math.max(leftInfo.max, max);
			min = Math.min(leftInfo.min, min);
		}
		if(rightInfo != null) {
			if(rightInfo.maxSubBSTSize > maxSubBSTSize) {
				maxSubBSTHead = rightInfo.maxSubBSTHead;
				maxSubBSTSize = rightInfo.maxSubBSTSize;
			}
			max = Math.max(rightInfo.max, max);
			min = Math.min(rightInfo.min, min);
		}
		// 与X节点有关
		boolean leftIsBST = leftInfo == null ? true : leftInfo.maxSubBSTHead ==  x.left;
		boolean rightIsBST = rightInfo == null ? true : rightInfo.maxSubBSTHead ==  x.right;
		if(leftIsBST && rightIsBST) {
			boolean leftMaxLess = leftInfo == null ? true : leftInfo.max < x.value;
			boolean rightMinMore = rightInfo == null ? true : rightInfo.min > x.value;
			if(leftMaxLess && rightMinMore) {
				maxSubBSTHead = x;
				maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize) + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
			}
		}
		return new Info(maxSubBSTHead, maxSubBSTSize, max, min);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		TreeNode head = null;
		TreeNode node1 = null;
		TreeNode node2 = null;
		boolean succed = true;
		for(int i = 0; i < maxTestTimes; i++) {
			head = generateRandomTreeNode(maxLevel, maxValue);
			node1 = maxSubBSTHeadUnRecursiveTricks(head);
			node2 = maxSubBSTHeadRecursiveTricks(head);
			if(node1 != node2) {
				succed = false;
				break;
			}
		}
		System.out.println(succed ? "Nice" : "ooVoo");
	}

	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

# 二叉树的递归套路深度实践八

给定一棵二叉树的头节点head，和另外两个节点a和b。 返回a和b的最低公共祖先

非递归之解题思路：

  • 遍历二叉树记录HashMap<TreeNode,TreeNode> map，key为节点，value为parent节点
  • 从a节点往上一直找，沿途使用HashSet<TreeNode>记录头节点
  • 从b节点往上一直找，并查找HashSet<TreeNode>中是否存在，若存在则返回公共祖先

递归套路之解题思路：

  • 以X节点为头的二叉树中返回a和b的最低公共祖先
  • 列出可能性：
    • 最低公共祖先与X节点无关
      • 左树上有a，b节点，获取左树上的最低公共祖先
      • 右树上有a，b节点，获取右树上的最低公共祖先
      • 左树与右树都没有a，b节点
    • 最低公共祖先与X节点有关
      • 左树上有a节点，右树上有b节点
      • 左树上有b节点，右树上有a节点
      • X是a节点，左树上有b节点或者右树上有b节点
      • X是b节点，左树上有a节点或者右树上有a节点
      • 以上都是X节点为最低公共祖先

代码：

package class12;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 * 	给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 	返回a和b的最低公共祖先
 * @author yangyanchao
 *
 */
public class Test08_LowestAncestor {
	/**
	 * 	二叉树节点信息
	 * @author yangyanchao
	 *
	 */
	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
	
	/**
	 * 	非递归套路版本
	 * @param head
	 * @return
	 */
	public static TreeNode lowestAncestorUnRecursiveTricks(TreeNode head, TreeNode a, TreeNode b) {
		if(head == null) {
			return null;
		}
		Map<TreeNode, TreeNode> parent = transformMapByTreeNode(head);
		HashSet<TreeNode> sets = new HashSet<>();
		TreeNode cur = a;
		while(cur != null) {
			sets.add(cur);
			cur = parent.get(cur);
		}
		cur = b;
		while(cur != null && !sets.contains(cur)) {
			cur = parent.get(cur);
		}
		return cur;
	}
	
	private static Map<TreeNode, TreeNode> transformMapByTreeNode(TreeNode head) {
		Map<TreeNode, TreeNode> parent = new HashMap<>();
		parent.put(head, null);
		transformMapProcess(head, parent);
		return parent;
	}

	private static void transformMapProcess(TreeNode head, Map<TreeNode, TreeNode> parent) {
		if(head.left != null) {
			parent.put(head.left, head);
			transformMapProcess(head.left, parent);
		}
		if(head.right != null) {
			parent.put(head.right, head);
			transformMapProcess(head.right, parent);
		}
	}

	/**
	 * 	递归套路版本
	 * @param head
	 * @return
	 */
	public static TreeNode lowestAncestorRecursiveTricks(TreeNode head, TreeNode a, TreeNode b) {
		if(head == null) {
			return null;
		}
		return process(head, a, b).lowestHead;
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public boolean isA;
		public boolean isB;
		public TreeNode lowestHead;
		public Info(boolean isA, boolean isB, TreeNode lowestHead) {
			this.isA = isA;
			this.isB = isB;
			this.lowestHead = lowestHead;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(TreeNode x, TreeNode a, TreeNode b) {
		if(x == null) {
			return new Info(false, false, null);
		}
		Info leftInfo = process(x.left, a, b);
		Info rightInfo = process(x.right, a, b);
		TreeNode lowestHead = null;
		boolean isA = x == a || leftInfo.isA || rightInfo.isA;
		boolean isB = x == b || leftInfo.isB || rightInfo.isB;
		if(leftInfo.isA && leftInfo.isB) {
			lowestHead = leftInfo.lowestHead;
		} else if(rightInfo.isA && rightInfo.isB) {
			lowestHead = rightInfo.lowestHead;
		} else if(isA && isB) {
			lowestHead = x;
		}
		return new Info(isA, isB, lowestHead);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 100000;
		int maxLevel = 10;
		int maxValue = 100;
		TreeNode lowestAncestor1 = null;
		TreeNode lowestAncestor2 = null;
		TreeNode node = null;
		TreeNode a = null;
		TreeNode b = null;
		boolean succed = true;
		for(int i = 0; i < maxTestTimes; i++) {
			node = generateRandomTreeNode(maxLevel, maxValue);
			a = randomTreeNode(node);
			b = randomTreeNode(node);
			lowestAncestor1 = lowestAncestorUnRecursiveTricks(node, a, b);
			lowestAncestor2 = lowestAncestorRecursiveTricks(node, a, b);
			if(lowestAncestor1 != lowestAncestor2) {
				succed = false;
				break;
			}
		}
		System.out.println(succed ? "Nice" : "ooVoo" );
	}

	private static TreeNode randomTreeNode(TreeNode node) {
		if (node == null) {
			return null;
		}
		List<TreeNode> list = new ArrayList<>();
		getListProcess(node, list);
		int randomIndex = (int) (Math.random() * list.size());
		return list.get(randomIndex);
	}

	private static void getListProcess(TreeNode node, List<TreeNode> list) {
		if(node == null) {
			return ;
		}
		list.add(node);
		getListProcess(node.left, list);
		getListProcess(node.right, list);
	}

	private static TreeNode generateRandomTreeNode(int maxLevel, int maxValue) {
		return generateRandomProcess(1, maxLevel, maxValue);
	}

	private static TreeNode generateRandomProcess(int i, int maxLevel, int maxValue) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int)(Math.random() * maxValue));
		head.left = generateRandomProcess(i + 1, maxLevel, maxValue);
		head.right = generateRandomProcess(i + 1, maxLevel, maxValue);
		return head;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

# 二叉树的递归套路深度实践九

派对的最大快乐值

员工信息的定义如下:

class Employee {
public int happy; // 这名员工可以带来的快乐值
List<Employee> subordinates; // 这名员工有哪些直接下级
}
1
2
3
4

公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。 叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。

这个公司现在要办party，你可以决定哪些员工来，哪些员工不来，规则： 1.如果某个员工来了，那么这个员工的所有直接下级都不能来 2.派对的整体快乐值是所有到场员工快乐值的累加 3.你的目标是让派对的整体快乐值尽量大 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

递归套路之解题思路：

  • 以x节点为头的整体最大快乐值
  • 列出可能性
    • x节点来的情况下最大的快乐值
      • x节点的快乐值加上直接下级不来的情况下的最大快乐值
    • x节点不来的情况下最大的快乐值
      • 直接下级来的情况下的最大快乐值和不来的情况下的最大快乐值取最大值相加

代码：

package class12;

import java.util.ArrayList;
import java.util.List;

/**
 * 	派对最大快乐值
 * @author yangyanchao
 *
 */
public class Test09_MaxHappy {
	/**
	 * 	员工信息
	 * @author yangyanchao
	 *
	 */
	public static class Employee {
		public int happy; // 这名员工可以带来的快乐值
		List<Employee> subordinates; // 这名员工有哪些直接下级
		public Employee(int happy) {
			this.happy = happy;
		}
	}
	
	/**
	 * 	非递归套路版本
	 * @param head
	 * @return
	 */
	public static int maxHappyUnRecursiveTricks(Employee head) {
		if(head == null) {
			return 0;
		}
		int yes = process1(head, true);
		int no = process1(head, false);
		return Math.max(yes, no);
	}
	
	private static int process1(Employee head, boolean yesOrNo) {
		if(head == null) {
			return 0;
		}
		int max = 0;
		if(yesOrNo) {
			max += head.happy;
		}
		for(Employee e : head.subordinates) {
			if(yesOrNo) {
				// 我来的时候 我的下级不能来了
				max += process1(e, !yesOrNo);
			} else {
				// 我不来的时候 我的下级可来可不来
				max += Math.max(process1(e, yesOrNo), process1(e, !yesOrNo));
			}
		}
		return max;
	}

	/**
	 * 	递归套路版本
	 * @param head
	 * @return
	 */
	public static int maxHappyRecursiveTricks(Employee head) {
		if(head == null) {
			return 0;
		}
		Info info = process(head);
		return Math.max(info.yes, info.no);
	}
	
	/**
	 * 	递归套路信息
	 * @author yangyanchao
	 *
	 */
	public static class Info {
		public int yes;// 我来的情况下的最大快乐值
		public int no;//  我不来的情况下的最大快乐值
		public Info(int yes, int no) {
			this.yes = yes;
			this.no = no;
		}
	}
	
	/**
	 * 	递归过程
	 * @param x
	 * @return
	 */
	public static Info process(Employee x) {
		if(x == null) {
			return new Info(0, 0);
		}
		int yes = x.happy;
		int no = 0;
		for(Employee sub : x.subordinates) {
			Info subInfo = process(sub);
			yes += subInfo.no;
			no += (Math.max(subInfo.yes, subInfo.no));
		}
		return new Info(yes, no);
	}
	
	public static void main(String[] args) {
		int maxTestTimes = 1000;
		int maxLevel = 10;
		int maxChildren = 10;
		int maxHappy = 100;
		int happy1 = 0;
		int happy2 = 0;
		Employee head = null;
		boolean succed = true;
		long time1 = System.currentTimeMillis();
		for(int i = 0; i < maxTestTimes; i++) {
			head = generateRandomComp(maxLevel, maxChildren, maxHappy);
			happy1 = maxHappyUnRecursiveTricks(head);
			happy2 = maxHappyUnRecursiveTricks(head);
			if(happy1 != happy2) {
				succed = false;
				System.out.println(happy1 + "  " + happy2);
				break;
			}
		}
		long time2 = System.currentTimeMillis();
		System.out.println(time2 - time1);
		System.out.println(succed ? "Nice" : "ooVoo");
	}

	private static Employee generateRandomComp(int maxLevel, int maxChildren, int maxHappy) {
		return generateRandomProcess(1, maxLevel, maxChildren, maxHappy);
	}

	private static Employee generateRandomProcess(int i, int maxLevel, int maxChildren, int maxHappy) {
		if(i > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Employee e = new Employee((int)(Math.random() * maxHappy));
		int childrenSize = (int)(Math.random() * maxChildren);
		e.subordinates = new ArrayList<>(childrenSize);
		for(int j = 0; j < childrenSize; j++) {
			e.subordinates.add(generateRandomProcess(i + 1, maxLevel, maxChildren, maxHappy));
		}
		return e;
	}
}
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

# 二叉树的递归套路深度实践十

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

来源：力扣（LeetCode） 链接：987. 二叉树的垂序遍历 (opens new window)

递归套路之解题思路：

  • 以X节点为头的二叉树返回二叉树的行、列、节点值对象的序列
  • 列出可能性
    • 左树的序列
    • 右树的序列
    • 然后排序
  • 向左、右两子树要信息(可能性求全集)
    • 高度height
    • 最大距离maxDistance

代码：
1

# 二叉树的递归套路总结

  • 可以解决面试中绝大多数的二叉树问题尤其是树型dp问题
  • 本质是利用递归遍历二叉树的便利性

dp -> dynamic programming -动态规划

套路总结：***** 很重要五星级别

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

← 第13节 贪心算法（上） →