樹

發表於 | 分類於 ，

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. 左右子樹之和