Binary Tree

題目

  • 226 Invert Binary Tree (Easy)

  • 114 Flatten Binary Tree to Linked List (Medium)

  • 116 Populating Next Right Pointers in Each Node (Medium)

  • 654 Maximum Binary Tree (Medium)

Construct Binary Tree from

  • 105 Construct Binary Tree from Preorder and Inorder Traversal (Medium)

  • 106 Construct Binary Tree from Inorder and Postorder Traversal (Medium)

  • 889 Construct Binary Tree from Preorder and Postorder Traversal (Medium)

  • 652 Find Duplicate Subtrees (Medium)

  • *297 Serialize and Deserialize Binary Tree (Hard)

  • 236 Lowest Common Ancestor of a Binary Tree (Medium)

  • 1373 Maximum Sum BST in Binary Tree (Hard)

  • 104 Maximum Depth of Binary Tree (Easy)

  • 543 Diameter of Binary Tree (Easy)

traverse

  • 94 Binary Tree Inorder Traversal (Easy)

  • 102 Binary Tree Level Order Traversal (Medium)

  • 107 Binary Tree Level Order Traversal II (Medium)

  • 103 Binary Tree Zigzag Level Order Traversal (Medium)

  • 144 Binary Tree Preorder Traversal (Easy)

  • 145 Binary Tree Postorder Traversal (Easy)

    Morris Traversal O(1) space O(n) time

  • 100 Same Tree (Easy)

  • 104 Maximum Depth of Binary Tree (Easy)

  • 111 Minimum Depth of Binary Tree (Easy)

  • 222 Count Complete Tree Nodes (Medium)

  • 501 Find Mode in Binary Search Tree (Easy)

N-ary Tree

  • 559 Maximum Depth of N-ary Tree (Easy)

  • 589 N-ary Tree Preorder Traversal (Easy)

  • 590 N-ary Tree Postorder Traversal (Easy)

  • 429 N-ary Tree Level Order Traversal

  • 965 Univalued Binary Tree (Easy)

  • 341 Flatten Nested List Iterator (Medium)

Path Sum

  • 112 Path Sum (Easy)
  • 113 Path Sum II (Medium)
  • *437 Path Sum III (Medium)
  • 129 Sum Root to Leaf Numbers (Medium)
  • *124 Binary Tree Maximum Path Sum (Hard)
  • 687 Longest Univalue Path

[補充]

  • 430 Flatten a Multilevel Doubly Linked List (Medium)
  • 117 Populating Next Right Pointers in Each Node II (Medium)
  • 637 Average of Levels in Binary Tree
  • 110 Balanced Binary Tree
  • 814 Binary Tree Pruning
  • 617 Merge Two Binary Trees (Easy)
  • 117 Populating Next Right Pointers in Each Node II (Medium)

觀念

快速排序是二元樹的前序遍歷,合併排序是二元樹的後序遍歷。

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
// 快速排序
void QuickSort(vector<int> &nums, int l, int r)
{

if (l < r)
{
int pivot = Partition(nums, l, r);
QuickSort(nums, l, pivot - 1);
QuickSort(nums, pivot + 1, r);
}
}

}
// 合併排序
void MergeSort(vector<int> &nums, int l, int r)
{

if (l < r)
{
int mid = (l + r) / 2;
MergeSort(nums, l, mid);
MergeSort(nums, mid + 1, r);
Merge(nums, l, mid, r);
}
}

寫有關於樹的演算法,或是說寫有關於遞迴演算法,關鍵一直都是必須搞清楚明確函數的定義是什麼,相信這個定義,不要跳入遞迴細節。

遍歷樹 框架

1
2
3
4
5
6
7
8
/* 二元樹遍歷框架 */
void traverse(TreeNode root) {
// 前序遍歷 TODO
traverse(root.left)
// 中序遍歷 TODO
traverse(root.right)
// 後序遍歷 TODO
}

Binary Search Tree

Binary Search Tree BST 中序遍歷是有序的

BST 框架

題目

  • 230 Kth Smallest Element in a BST (Medium)
  • 538 Convert BST to Greater Tree (Medium)
  • 1038 Binary Search Tree to Greater Sum Tree (Medium)

operation

  • 450 Delete Node in a BST (Medium)

  • 701 Insert into a Binary Search Tree (Medium)

  • 700 Search in a Binary Search Tree (Easy)

  • 98 Validate Binary Search Tree (Medium)

  • 96 Unique Binary Search Trees (Medium)

  • 95 Unique Binary Search Trees II (Medium)

  • 1373 Maximum Sum BST in Binary Tree (Hard)

  • 501 Find Mode in Binary Search Tree (Easy)

  • 530 Minimum Absolute Difference in BST (Easy)

  • 783 Minimum Distance Between BST Nodes (Easy)

  • 235 Lowest Common Ancestor of a Binary Search Tree (Easy)

觀念

判斷 BST 的合法性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制,说明不是合法 BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val,右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, 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
// option 1 brute force
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target) return true;
// 当前节点没找到就递归地去左右子树寻找
return isInBST(root.left, target)
|| isInBST(root.right, target);
}

// option 2 binary search 真正BST精神
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val < target)
return isInBST(root.right, target);
if (root.val > target)
return isInBST(root.left, target);
// root 该做的事做完了,顺带把框架也完成了,妙
}
// 抽象出來
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标,做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}

插入一個數,涉及到“改”,就要返回樹的結構

1
2
3
4
5
6
7
8
9
10
11
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}

刪除一個數,先“查“再”改“。找到後判斷是否有子節點,及是否破壞結構

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
// 抽象 框架
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// 找到啦,进行删除
} else if (root.val > key) {
// 去左子树找
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// 去右子树找
root.right = deleteNode(root.right, key);
}
return root;
}


TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}

TreeNode getMin(TreeNode node) {
// BST 最左边的就是最小的
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
TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums is empty) return null;
// 找到数组中的最大值
int maxVal = Integer.MIN_VALUE;
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
index = i;
}
}

TreeNode root = new TreeNode(maxVal);
// 递归调用构造左右子树
root.left = constructMaximumBinaryTree(nums[0..index-1]);
root.right = constructMaximumBinaryTree(nums[index+1..nums.length-1]);
return root;
}

不同的二元搜尋樹,求樹的數量、列出每棵樹

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

/* 主函数 */
int numTrees(int n) {
// 计算闭区间 [1, n] 组成的 BST 个数
return count(1, n);
}

/* 计算闭区间 [lo, hi] 组成的 BST 个数 */
int count(int lo, int hi) {
// base case
if (lo > hi) return 1;

int res = 0;
for (int i = lo; i <= hi; i++) {
// i 的值作为根节点 root
int left = count(lo, i - 1);
int right = count(i + 1, hi);
// 左右子树的组合数乘积是 BST 的总数
res += left * right;
}

return res;
}

// 备忘录
int[][] memo;

int numTrees(int n) {
// 备忘录的值初始化为 0
memo = new int[n + 1][n + 1];
return count(1, n);
}

int count(int lo, int hi) {
if (lo > hi) return 1;
// 查备忘录
if (memo[lo][hi] != 0) {
return memo[lo][hi];
}

int res = 0;
for (int mid = lo; mid <= hi; mid++) {
int left = count(lo, mid - 1);
int right = count(mid + 1, hi);
res += left * right;
}
// 将结果存入备忘录
memo[lo][hi] = res;

return res;
}


/* 主函数 */
public List<TreeNode> generateTrees(int n) {
if (n == 0) return new LinkedList<>();
// 构造闭区间 [1, n] 组成的 BST
return build(1, n);
}

/* 构造闭区间 [lo, hi] 组成的 BST */
List<TreeNode> build(int lo, int hi) {
List<TreeNode> res = new LinkedList<>();
// base case
if (lo > hi) {
res.add(null);
return res;
}

// 1、穷举 root 节点的所有可能。
for (int i = lo; i <= hi; i++) {
// 2、递归构造出左右子树的所有合法 BST。
List<TreeNode> leftTree = build(lo, i - 1);
List<TreeNode> rightTree = build(i + 1, hi);
// 3、给 root 节点穷举所有左右子树的组合。
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {
// i 作为根节点 root 的值
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}

return res;
}

Graph 圖,用adjacent linked list 、adjacent matrix 存儲

遍歷圖的框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 多叉树遍历框架 */
void traverse(TreeNode root) {
if (root == null) return;

for (TreeNode child : root.children)
traverse(child);
}

// 有環的圖
Graph graph;
boolean[] visited;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
if (visited[s]) return;
// 经过节点 s
visited[s] = true;
for (TreeNode neighbor : graph.neighbors(s))
traverse(neighbor);
// 离开节点 s
visited[s] = false;
}

圖的所有路徑

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
// 记录所有路径
List<List<Integer>> res = new LinkedList<>();

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
LinkedList<Integer> path = new LinkedList<>();
traverse(graph, 0, path);
return res;
}

/* 图的遍历框架 */
void traverse(int[][] graph, int s, LinkedList<Integer> path) {

// 添加节点 s 到路径
path.addLast(s);

int n = graph.length;
if (s == n - 1) {
// 到达终点
res.add(new LinkedList<>(path));
path.removeLast();
return;
}

// 递归每个相邻节点
for (int v : graph[s]) {
traverse(graph, v, path);
}

// 从路径移出节点 s
path.removeLast();
}

二元搜尋數子樹的最大鍵值總和

  1. 確認子樹合法性(BST左小右大)
  2. 確認把自己加入是否還合法,比較左子樹最大值和柚子樹最小值
  3. 左右子樹之和