二叉树
# 二叉树
# 递归序
先序遍历：头节点 左节点 右节点
中序遍历：左节点 头节点 右节点
后序遍历：左节点 右节点 头节点
public static class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
public static void f(Node head) {
if(head == null) {
return;
}
System.out.println("先序遍历"+head.val); //头节点 左节点 右节点
f(head.left);
// System.out.println("中序遍历"+head.val); //左节点 头节点 右节点
f(head.right);
// System.out.println("后序遍历"+head.val); //左节点 右节点 头节点
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(8);
f(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
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
# 非递归版遍历二叉树顺序
使用 Stack 类 手动压栈出栈
# 先序
- push 头节点到栈顶 再 pop 弹出并输出
- 先 push 右节点 到栈中 压为栈底
- 再 push 左节点 到栈中 压为栈顶 重复上述步骤
//先序遍历 头 左 右
public static void pre(Node head) {
System.out.println("先序遍历");
if(head != null) {
Stack<Node> stack = new Stack<>();
stack.add(head);
while(!stack.isEmpty()) {
head = stack.pop(); //删除栈顶
System.out.println(head.value);
//先push右树 压入栈底
if(head.right != null) {
stack.push(head.right);
}
//再push左树 压入栈顶
if(head.left != null) {
stack.push(head.left);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 2 个栈实现后序
上面我们使用 1 个栈实现了，先序遍历头左右的顺序，我们知道后序遍历为左右头，我们微调一下压入左右树的顺序，实现了头右左的顺序，准备第二个栈按顺序压入，再进行弹出成了左右头的顺序。
//两个栈 实现后序遍历
public static void pos1(Node head) {
System.out.println("后序遍历");
if(head !=null) {
Stack<Node> s1= new Stack<>();
Stack<Node> s2= new Stack<>();
s1.add(head);
while(!s1.isEmpty()) {
head = s1.pop();
s2.push(head);//头节点压入栈 s2栈底
if(head.left != null) {
s1.push(head.left); //左节点 入s1栈底
}
if(head.right != null) { //右节点 入s1栈 此时为栈顶
s1.push(head);
}
//此时s1栈存储为 [右,左]
//s2栈为 [头] 两栈结合为 [左,右,头]
}
// 左 右 头
while(!s2.isEmpty()) {
System.out.println(s2.pop().value);
}
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 1 个栈实现后序
// 一个栈 实现后序遍历
public static void pos2(Node head) {
System.out.println("后序遍历2");
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.push(head);
Node cur = null;
Node pre = null;
while (!stack.isEmpty()) {
cur = stack.peek(); // 只查看栈顶不删除
// 不断将左树入栈 栈顶为左树的叶子节点 pre为了防止之前入过栈的左右节点 重新入栈
if (cur.left != null && pre != cur.left && pre != cur.right) {
stack.push(cur.left);
// 左树无节点/已经入过栈 将右树入栈
} else if (cur.right != null && pre != cur.right) {
stack.push(cur.right);
} else {
// 左右都无节点 直接删除当前栈顶 为头节点
System.out.println(stack.pop().value);
pre = cur;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 中序
// 中序遍历 左 头 右
public static void in(Node cur) {
System.out.println("中序遍历");
if (cur != null) {
Stack<Node> statck = new Stack<>();
while (!statck.isEmpty() || cur != null) {
if (cur != null) {
statck.push(cur);
cur = cur.left; // 遍历根节点 左树叶子节点 入栈
} else {
cur = statck.pop(); // 弹出栈
System.out.println(cur.value);
cur = cur.right;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 前缀树
# 二叉树按层变遍历
即宽度优先搜索 (BFS) 使用队列实现
//按层遍历二叉树 bfs
public static void levle(Node head) {
if(head ==null) {
return;
}
LinkedList<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
if(cur.left != null) {
queue.add(head.left);
}
if(cur.right != null) {
queue.add(head.right);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 二叉树序列化和反序列化
# 先序遍历序列化
只有先序和后序遍历可以序列化，而中序遍历序列化时会有歧义（即两个节点位置不确定）
// 先序 序列化二叉树
public static Queue<String> preSerial(Node head) {
if (head == null) {
return null;
}
Queue<String> queue = new LinkedList<>();
pres(head, queue);
return queue;
}
private static void pres(Node head, Queue<String> queue) {
if (head == null) {
queue.add(null); // null节点 入栈
} else {
queue.add(String.valueOf(head.value)); // 头节点压栈
pres(head.left, queue);
pres(head.right, queue);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 按层遍历序列化
// 先序 反序列化二叉树
public static Node buildByPreQueue(Queue<String> queue) {
if (queue == null || queue.size() == 0) {
return null;
}
return preb(queue);
}
private static Node preb(Queue<String> queue) {
String value = queue.poll();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = preb(queue);
head.right = preb(queue);
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 431.Encode N-ary Tree to Binary Tree (opens new window)
设计一种算法，将 N 叉树编码为二叉树，并对二叉树进行解码，得到原始 N 叉树。N-ary 树是一个有根树，其中每个节点不超过 N 个子节点。类似地，二叉树是一个有根树，其中每个节点的子节点不超过 2 个。您的编码 / 解码算法的工作方式没有限制。您只需要确保可以将 N 叉树编码为二叉树，并且可以将二叉树解码为原始的 N 叉树结构。
例如，您可以通过 3-ary 这种方式将以下树编码为二叉树：
请注意，以上只是一个可能会或可能不会起作用的示例。您不一定需要遵循这种格式，因此请发挥创造力并自己提出不同的方法。
思路:
将多叉树的孩子节点 全部挂载左树的右边界
public static class Node {
public int val;
public List<Node> children;
public Node() {
}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children; // 节点下所有孩子(即有多少个这个节点就有多少叉)
}
};
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Codec {
// 将多叉树 序列化为二叉树
public TreeNode encode(Node root) {
if (root == null) {
return null;
}
TreeNode head = new TreeNode(root.val);// 先建立 根节点
head.left = en(root.children); // 将孩子节点(多叉树)收为二叉树
return head;
}
// 孩子节点第一个全部挂载左树 剩下的孩子节点挂载在新建左树节点的右树
private TreeNode en(List<Node> children) {
TreeNode head = null;
TreeNode cur = null;
for (Node node : children) {
TreeNode tNode = new TreeNode(node.val); // 当前孩子 新生成节点
if (head == null) {
// 当前节点为孩子节点第一个节点 应为新生成的节点
head = tNode;
} else {
// 否则应挂载上一个孩子节点的(head)的右树下
head.right = tNode;
}
cur = head; // 缓存当前头
cur.left = en(node.children); // 深度优先 建立根节点左树
}
return head;
}
// 将二叉树反序列化为 多叉树
public Node decode(TreeNode root) {
if (root == null) {
return null;
}
return new Node(root.val, de(root.left));
}
private List<Node> de(TreeNode root) {
ArrayList<Node> childern = new ArrayList<>();
while (root != null) {
Node cur = new Node(root.val, de(root.left)); //先深度优先 递归到左树叶子节点
childern.add(cur); //将当前节点加入链表集合中
root = root.right; //再while循环 将当前节点(即左树)的孩子节点 不断加入集合中
}
return childern;
}
}
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
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
# 求二叉树最大宽度
使用宽度优先搜索
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
public static int maxWidth(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
int max = 0;
int curWidth = 0; // 当前层宽度
Node curEnd = head; // 当前层尾元素
Node nextEnd = null; // 下一层尾元素
while (!queue.isEmpty()) {
Node cur = queue.poll();
curWidth++; // 增加宽度
if (cur.left != null) { // 是否有左右树
queue.add(cur.left); // 入栈
nextEnd = cur.left; // 更新下一层尾元素
}
if (cur.right != null) {
queue.add(cur.right);
nextEnd = cur.right;
}
if (cur == curEnd) {
max = Math.max(max, curWidth);
curWidth = 0; // 重置当前宽度
curEnd = nextEnd; // 更新当前尾元素 为下一层尾元素
}
}
return max;
}
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
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
# 求二叉树某个节点的后继节点
首先我们可以通过中序遍历的方式 知道某个节点的后续节点 根据中序遍历 (左 头 右) 的规则我们可以推断出
- 如果 x 节点有右树 后继节点为右孩子 最深的左节点
- 如果 x 节点为无右树 后继节点为离 x 节点最近的父辈节点并且该父辈节点以左节点形式存在
- 不断往上找父辈节点 并且此父辈节点是以左孩子形式存在 此时会命中
parent.rigth != nodewhile 循环结束 返回此父辈节点为后继节点 - 不断往上找父辈节点 但父辈节点全为右孩子形式 此时会命中
parent == nullwhile 循环结束 此时会返回父辈节点 (此时父辈节点为 null 当前节点没有后继节点)
- 不断往上找父辈节点 并且此父辈节点是以左孩子形式存在 此时会命中
- 如果 x 节点无右树并为左节点 后续节点为父节点
根据上述规则我们可以给每个节点添加一个 parent 指针 (存储为父节点地址)，通过 parent 指针可以找到此节点的父节点
public static class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
public static Node getSuccessorNode(Node node) {
if (node == null) {
return null;
}
// 如果查找的节点存在右孩子 查询右树的最深的左树
if (node.right != null) {
return getLeftMost(node.right);
} else {
// 如果查找的节点不存在右孩子
Node parent = node.parent;//查询节点的父节点
/**
* 1.如果当前查找节点为父节点的左孩子 while循环不成立 直接返回父节点即可
* 2.如果当前查找节点为父节点的右孩子 while循环成立 查找最近的父辈节点并且该父辈节点以左节点形式存在
* 2.1 不断往上找父辈节点 并且此父辈节点是以左孩子形式存在 此时会命中 `parent.rigth != node`while循环结束 返回此父辈节点为后继节点
* 2.2不断往上找父辈节点 但父辈节点全为右孩子形式 此时会命中 `parent == null`while循环结束 此时会返回父辈节点(此时父辈节点为null 当前节点没有后继节点)
*/
while (parent != null && parent.right == node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
private static Node getLeftMost(Node node) {
while (node.left != null) {
node = node.left; // 最深的 左节点
}
return node;
}
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
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
# 折纸问题
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折 1 次，压出折痕后展开 此时折痕是凹下去的，即折痕突起的方向指向纸条的背面 如果从纸条的下边向上方连续对折 2 次，压出折痕后展开 此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。 给定一个输入参数 N，代表纸条都从下边向上方连续对折 N 次 请从上到下打印所有折痕的方向。 N=1 时，打印: down N=2 时，打印: down down up
思路:
其实为一个比较特殊的二叉树的中序遍历，头节点为凹，左子树必定为凹，右子树必定为凸，满足以上条件中序遍历既可。
public static void printAllFolds(int 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 判断是否为完全二叉树
一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
特征: 叶子结点只可能在最大的两层出，即叶子节点从左到右中间不可能出现空缺，要么出现在最后第二层和第一层。如叶子节点往下遇到 null 后往后的叶子节点左右节点必须为 null，满足此规则即可。
如下图所示
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)) //leaf变为true 说明之前遇到了null节点
||
(l == null && r != null) //左树为null 右树不为null 根节点出现空缺返回false
) {
return false;
}
//有左孩子 入队列
if (l != null) {
queue.add(l);
}
//有右孩子 入队列
if (r != null) {
queue.add(r);
}
//因为是按层遍历 到根节点了 标记变量改为true
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
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
# 二叉树的递归套路
- 假设以 X 节点为头，假设可以向 X 左树和 X 右树要任何信息
- 在上一步的假设下，讨论以 X 为头节点的树，得到答案的可能性（最重要）
- 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
- 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息 S
- 递归函数都返回 S，每一棵子树都这么要求
- 写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
# 求二叉树最大距离
给定一棵二叉树的头节点 head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
最大距离必须为最优路径
- 最大距离存在左树中 不经过根节点
- 最大距离存在右树中 不经过根节点
- 最大距离不存在左右树中 必经过根节点 左树高度 + 右树高度 + 1
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class info{
public int maxDistance; //最大距离
public int height; //高度
public info(int maxDistance, int height) {
this.maxDistance = maxDistance;
this.height = height;
}
}
public static int maxDistance2(Node head) {
return process(head).maxDistance;
}
//深度优先
private static info process(Node head) {
if(head == null) {
return new info(0, 0); //为空null 高度为0 最大距离为0
}
info leftInfo = process(head.left);
info rightInfo = process(head.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
28
29
30
31
32
33
34
35
36
37
38
39
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
# 判断是否为满二叉树
判断方法一：收集整颗树的高度和节点数，只有满二叉树满足
判断方法二：左树 和 右树为满，并且左右树高度一致，则为满二叉树
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class info1 {
int height;
int nodes;
public info1(int height, int nodes) {
this.height = height;
this.nodes = nodes;
}
}
// 只有满二叉树满足 : 2 ^ h - 1 == n
public static boolean isFull1(Node head) {
if (head == null) {
return true;
}
info1 allInfo = process1(head);
return (1 << allInfo.height) - 1 == allInfo.nodes;
}
private static info1 process1(Node head) {
if (head == null) {
return new info1(0, 0); // 节点空返回高度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 isFull, int height) {
this.isFull = isFull;
this.height = height;
}
}
private static info2 process2(Node head) {
if (head == null) {
return new info2(true, 0);
}
info2 leftInfo = process2(head.left);
info2 rightInfo = process2(head.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
75
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
# 求二叉树中最大的二叉搜索子树的大小
给定一棵二叉树的头节点 head，返回这颗二叉树中最大的二叉搜索子树的大小
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
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(Node head) {
if (head == null) {
return null;
}
info leftInfo = process(head.left);
info rightInfo = process(head.right);
int max = head.value; // 假设为自身
int min = head.value;
int allSize = 1; // 所有字节节数 算上自身
if (leftInfo != null) {
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
allSize += leftInfo.allSize; // 加上左树的子节点数
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
allSize += rightInfo.allSize; //加上右树的字节点数
}
int p1 = -1;
if (leftInfo != null) {
p1 = leftInfo.maxBSTSubtreeSize;
}
int p2 = -1;
if (rightInfo != null) {
p2 = rightInfo.maxBSTSubtreeSize;
}
int p3 = -1;
//判断最大子树大小 与 所有节点数 是否相等(即没有断层)
boolean leftBst = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
boolean rightBst = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
if (leftBst && rightBst) {
// 验证当前节点是否满足二叉树规则 左孩子比自身小 右孩子比自身大
boolean leftMaxLeesX = leftInfo == null ? true : (leftInfo.max < head.value);
boolean rightMinMoreX = rightInfo == null ? true : (head.value < rightInfo.min);
if (leftMaxLeesX && 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);
}
public static int maxSubBSTSize2(Node head) {
if(head == null) {
return 0;
}
return process(head).maxBSTSubtreeSize;
}
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
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
# 递归套路版判断是否为完全二叉树
上面我们使用队列按层遍历 (bfs) 来判断是否为完全二叉树，我们可以改为递归版本使用递归套路
# 求二叉树最大的二叉搜索树的头节点
给定一棵二叉树的头节点 head，返回这颗二叉树中最大的二叉搜索子树的头节点
# 求二叉树上 a 和 b 两节点的最低公共祖先
给定一棵二叉树的头节点 head，和另外两个节点 a 和 b，返回 a 和 b 的最低公共祖先
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class info {
boolean findA;
boolean findB;
Node ans;
public info(boolean findA, boolean findB, Node ans) {
this.findA = findA;
this.findB = findB;
this.ans = ans;
}
}
public static Node lowestAncestor2(Node head, Node a, Node b) {
if (head == null) {
return null;
}
return process(head, a, b).ans;
}
private static info process(Node head, Node a, Node b) {
if (head == null) {
return new info(false, false, null); // 空节点 返回info信息
}
info leftInfo = process(head.left, a, b); // 递归下去
info rightInfo = process(head.right, a, b);
boolean findA = (head == a) || leftInfo.findA || rightInfo.findA; // 如果a/b为自身 或者 左右info之前发现过a/b为true
boolean findB = (head == b) || leftInfo.findB || rightInfo.findB;
Node ans = null; // 先初始化
if (findA && findB) { // a和b都标记找到
if (leftInfo.ans != null) { // 之前leftInfo有标记过祖先，继承之前的祖先，因为题目要求是最低祖先（最先找到的祖先）
ans = leftInfo.ans;
} else if (rightInfo.ans != null) { // right同理
ans = rightInfo.ans;
} else {
ans = head; // 之前都没有标记过祖先 即当前节点为最先发现的祖先
}
}
return new info(findA, findB, ans); // 返回info信息
}
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
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
# 派对的最大快乐值
公司的每个员工都符合 Employee 类的描述。整个公司的人员结构可以看作是一棵标准的、 没有环的多叉树 树的头节点是公司唯一的老板，除老板之外的每个员工都有唯一的直接上级 叶节点是没有任何下属的基层员工 (subordinates 列表为空)，除基层员工外每个员工都有一个或多个直接下级 这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来，规则：
如果某个员工来了，那么这个员工的所有直接下级都不能来
派对的整体快乐值是所有到场员工快乐值的累加
你的目标是让派对的整体快乐值尽量大
给定一棵多叉树的头节点 boss，请返回派对的最大快乐值。
public static class Employee {
public int happy;
public List<Employee> nexts;
public Employee(int h) {
happy = h;
nexts = new ArrayList<>();
}
}
public static class info {
int no; // 当前节点不来的情况
int yes; // 当前节点来的情况
public info(int no, int yes) {
super();
this.no = no;
this.yes = yes;
}
}
public static int maxHappy2(Employee head) {
info allInfo = process(head);
return Math.max(allInfo.no, allInfo.yes);
}
private static info process(Employee head) {
if (head == null) {
return new info(0, 0);
}
int no = 0;// 不来的情况
int yes = head.happy; // 来的情况
for (Employee employee : head.nexts) {
info nextInfo = process(employee);
no += Math.max(nextInfo.no, nextInfo.yes);// 子节点可来可不来
yes += nextInfo.no; // 当前节点来了 他的下属子节点必须得不来
}
return new info(no, yes);
}
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
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
# 100. 相同的树 (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null ^ q == null) { //有一个为空 另外一个不为空 返回
return false;
}
if (p == null && q == null) { //两者都为空
return true;
}
//两者值相等 && 左树相等 && 右树相等
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
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
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
# 101. 对称二叉树 (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSameTree(root,root);//自己与自己比较
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null ^ q == null) { //有一个为空 另外一个不为空 返回
return false;
}
if (p == null && q == null) { //两者都为空
return true;
}
//两者值相等 && 左树与`右树相等 && 右树与`左树相等
return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
}
}
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
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
# 104. 二叉树的最大深度 (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
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
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
# 105. 从前序与中序遍历序列构造二叉树 (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
Map<Integer, Integer> IndexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
IndexMap.put(inorder[i], i);
}
return f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1,IndexMap);
}
private TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2,Map<Integer, Integer> IndexMap) {
if (l1 > r1) { //
return null;
}
TreeNode head = new TreeNode(preorder[l1]); // 头节点
if (l1 == r1) { // 只有一个元素时
return head;
}
int index = IndexMap.get(preorder[l1]); // 查找当前头节点在中序遍历数组的位置
// 左树构建 l1+1到 l1 + index - l2 为左树的先序遍历范围 l2到index-1为中序遍历范围
head.left = f(preorder, l1 + 1, l1 + index - l2, inorder, l2, index - 1,IndexMap); // 注意左树和右树构建采用的遍历范围均相同长度
// 右树构建 l1 + index - l2(即左树的结束范围) +1 到 r1为右树先序遍历范围 index+1到r2为右树中序遍历的范围
head.right = f(preorder, l1 + index - l2 + 1, r1, inorder, index + 1, r2,IndexMap);
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
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
# 107. 二叉树的层序遍历 II (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) { // 根节点为空直接返回空列表
return ans;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root); // 将头节点加入队列中
while (!queue.isEmpty()) {
int size = queue.size(); // 获取队列当前长度
List<Integer> tans = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode temp = queue.poll();
tans.add(temp.val); // 获取头节点的值 放入局部队列中
if (temp.left != null) {
queue.add(temp.left); // 左节点非空 加入到队列中
}
if (temp.right != null) {
queue.add(temp.right); // 右节点非空 加入队列中
}
}
ans.add(0, tans); // 将上次队列缓存头节点清空后的节点值加入到结果集合中
}
return ans;
}
}
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
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
# 110. 平衡二叉树 (opens new window)
平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isBalanced(TreeNode root) {
return process(root).isBalanced; //直接返回root节点的信息
}
public class info {
public boolean isBalanced; // 是否为平衡二叉树
public int height; // 高度
public info(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
public info process(TreeNode root) {
if (root == null) { // 空节点
return new info(true, 0);
}
info leftInfo = process(root.left); // 左树信息
info rightInfo = process(root.right); // 右树信息
int height = Math.max(leftInfo.height, rightInfo.height) + 1; // 当前节点高度为 左和右树最大值 +1
boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
&& Math.abs(leftInfo.height - rightInfo.height) <= 1; //左树和右树为平衡二叉树 并且 左右树高度差不大于1
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
# 98. 验证二叉搜索树 (opens new window)
搜索二叉树: 左树的值比根节点的值小，右树的值比根节点的值大
一颗搜索二叉树中序遍历是递增顺序
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isValidBST(TreeNode root) {
return isBST(root).isBst;
}
public class info{
boolean isBst;
int max;
int min;
public info(boolean isBst, int max, int min) {
this.isBst = isBst;
this.max = max;
this.min = min;
}
}
public info isBST(TreeNode root) {
if(root == null) { //头节点为空则返回空
return null;
}
info leftinfo = isBST(root.left); //递归进入左树
info rightinfo = isBST(root.right); //递归进入右树
int max = root.val; //假设最大值为自身
int min = root.val;//假设最小值为自身
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 bst = true; //先假设为搜索二叉树
if(leftinfo !=null && !leftinfo.isBst) { //如果左树不满足则 头节点标记为不是二叉树
bst =false;
}
if(rightinfo !=null && !rightinfo.isBst) { //如果右树不满足则 头节点标记为不是二叉树
bst =false;
}
boolean lefiBst = leftinfo == null ? true : (leftinfo.max < root.val); //如果左树信息为空返回ture 否则左树最大值必须小于当前节点值
boolean rightBst = rightinfo == null ? true : (rightinfo.min > root.val);//如果右树信息为空返回ture 否则右树最小值必须大于当前节点值
if(!lefiBst || !rightBst) { //不满足搜索二叉树规则
bst = false;
}
return new info(bst, 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
68
69
70
71
72
73
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
# 112. 路径总和 (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public boolean isSum = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root ==null) { //根节点为空 直接返回false
return false;
}
tree(root, 0, targetSum);
return isSum;
}
public void tree(TreeNode root, int preSum, int sum) {
if (root.left == null && root.right == null) { //当前头节点左右子节点都为空
if (preSum + root.val == sum) { //当前头节点值与上次sum 为target则找到
isSum = true;
}
return;
}
preSum += root.val; //累加当前sum
if (root.left != null) { //左节点有叶节点 递归进去
tree(root.left, preSum, sum);
}
if (root.right != null) { //右节点有叶节点 递归进去
tree(root.right, preSum, sum);
}
}
}
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
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
# 113. 路径总和 II (opens new window)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
ArrayList<Integer> path = new ArrayList<>();
process(root, path, 0, targetSum, ans);
return ans;
}
public void process(TreeNode root, ArrayList<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
if (root.left == null & root.right == null) {
if (root.val + preSum == sum) {
path.add(root.val); // 添加当前节点路径
// List<Integer> newPath = copy(path); // 拷贝
List<Integer> newPath = (List<Integer>) path.clone(); // 本质上是浅拷贝 但里面存储的是值 所以复制了里面值 如里面存储的是引用不应用深拷贝
ans.add(newPath); // 添加到结果集合中
path.remove(path.size() - 1); // 删除当前路径
}
}
preSum += root.val; // 累加 无需回溯 因为是值传递 不是引用传递
path.add(root.val); // 记录节点
if (root.left != null) { // 递归
process(root.left, path, preSum, sum, ans);
}
if (root.right != null) { // 递归
process(root.right, path, preSum, sum, ans);
}
path.remove(path.size() - 1); // 恢复现场
}
}
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
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
编辑 (opens new window)
上次更新: 2023/12/06, 01:31:48