Tree

由 n 個有限節點組成一個具有層次關係的集合，形狀類似一顆倒著的樹，具有以下幾個特點：

  • 沒有環 (cycle)。
  • 所有點之間連通，且只有唯一路徑。
  • 邊數 = 點數 - 1。

Binary Tree

每個節點的度數不大於 2 的樹，左右的分支分別稱為 左子樹與右子樹，並且左右子樹有次序關係，不能隨意交換。

遍歷

  • 前序遍歷 (根結點 -> 左子樹 -> 右子樹)
  • 中序遍歷 (左子樹 -> 根結點 -> 右子樹)
  • 後序遍歷 (左子樹 -> 右子樹 -> 根結點)
1
2
3
4
5
6
7
8
9
void treeTraversal(TreeNode* root) {
    if(root == nullptr) return;
    //對根節點的操作 - 前序
    treeTraversal(root -> left);
    //對根節點的操作 - 中序
    treeTraversal(root -> right);
    //對根節點的操作 - 後序
    return;
}
  • 層序遍歷
    紀錄 queue 的大小，每次處理一整層的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int n;
        if(root != nullptr) q.push(root);
        while(!q.empty()){
            n = q.size();
            for(int i = 0; i < n; i++){
                //對節點的操作
                if(q.front() -> left != nullptr) q.push(q.front() -> left);
                if(q.front() -> right != nullptr) q.push(q.front() -> right);
                q.pop();
            }
        }
        return;
    }

還原

透過二叉樹的遍歷結果回推原始二叉樹的結構。

前序 + 中序

前序遍歷的順序為 [根結點、左子樹、右子樹]，而中序遍歷的順序為 [左子樹、根結點、右子樹]，因此我們可以透過前序遍歷的第一個元素找到根結點，將其帶入中序遍歷，就可以找到左、右子樹，對左、右子樹遞迴進行此行為就可以構造出原始樹。

1
2
3
4
5
6
7
8
9
10
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if(preorder.size() == 0) return nullptr;
    int len = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();
    vector<int> pre_left(preorder.begin() + 1, preorder.begin() + 1 + len);
    vector<int> pre_right(preorder.begin() + 1 + len, preorder.end());
    vector<int> in_left(inorder.begin(), inorder.begin() + len);
    vector<int> in_right(inorder.begin() + 1 + len, inorder.end());
    TreeNode* root = new TreeNode(preorder[0], buildTree(pre_left, in_left), buildTree(pre_right, in_right));
    return root;
}

後序 + 中序

與前序 + 中序類似，因此我們可以透過後序遍歷的最後一個元素找到根結點，將其帶入中序遍歷，就可以找到左、右子樹，對左、右子樹遞迴進行此行為就可以構造出原始樹。

1
2
3
4
5
6
7
8
9
10
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if(inorder.size() == 0) return nullptr;
    int len = find(inorder.begin(), inorder.end(), postorder[postorder.size() - 1]) - inorder.begin();
    vector<int> post_left(postorder.begin(), postorder.begin() + len);
    vector<int> post_right(postorder.begin() + len, postorder.end() - 1);
    vector<int> in_left(inorder.begin(), inorder.begin() + len);
    vector<int> in_right(inorder.begin() + 1 + len, inorder.end());
    TreeNode* root = new TreeNode(postorder[postorder.size() - 1], buildTree(in_left, post_left), buildTree(in_right, post_right));
    return root;
}

前序 + 後序

因為無法確定左右子樹的區分，因此構造出的樹不唯一，這邊假設前序遍歷的第二個元素 preorder[1] 是左子樹的根結點，可以構造出其中一種樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
    if(preorder.size() == 0) return nullptr;
    if(preorder.size() == 1){
        TreeNode* root = new TreeNode(preorder[0]);
        return root;
    }
    int len = find(postorder.begin(), postorder.end(), preorder[1]) - postorder.begin() + 1;
    vector<int> pre_left(preorder.begin() + 1, preorder.begin() + 1 + len);
    vector<int> pre_right(preorder.begin() + 1 + len, preorder.end());
    vector<int> post_left(postorder.begin(), postorder.begin() + len);
    vector<int> post_right(postorder.begin() + len, postorder.end() - 1);
    TreeNode* root = new TreeNode(preorder[0], constructFromPrePost(pre_left, post_left), constructFromPrePost(pre_right, post_right));
    return root;
}

練習

LeetCode 112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:
Input: root = [], targetSum = 0
Output: false

Solution:

1
2
3
4
5
6
7
8
class Solution {
public:
    bool hasPathSum(TreeNode* root, int t) {
        if(root == nullptr) return false;
        if(root -> left == nullptr && root -> right == nullptr && t - root -> val == 0) return true;
        return hasPathSum(root -> left, t - root -> val) || hasPathSum(root -> right, t - root -> val);
    }
};

如果當前節點為葉節點且離 targetSum 的差距為 0，代表滿足目標，否則將 targetSum - root -> val 作為參數傳入左右節點，並遞迴判斷是否成立。

LeetCode 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q) return root;
        if(root != nullptr){
            TreeNode* l = lowestCommonAncestor(root -> left, p, q);
            TreeNode* r = lowestCommonAncestor(root -> right, p, q);
            if(l != nullptr && r != nullptr) return root;
            if(l == nullptr) return r;
            else return l;
        }
        return nullptr;
    }
};

如果函數回傳的值為nullptr 代表 p,q 都不在這個子樹中，因此根據左右子樹帶入函數的值，可以區分為以下幾種情形：

  • l != nullptr && r != nullptr 代表 p,q 分別位於左右子樹，則該節點為最低共同祖先。
  • l == nullptr && r != nullptr 代表 p,q 都位於右子樹。
  • l != nullptr && r !== nullptr 代表 p,q 都位於左子樹。
  • l != nullptr && r != nullptr 代表 p,q 不在這個子樹中。

LeetCode 124. Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int ans = INT_MIN;
    int pathSum(TreeNode* root) {
        if(root == nullptr) return 0;
        int left = max(0, pathSum(root -> left));
        int right = max(0, pathSum(root -> right));
        ans = max(ans, left + right + root -> val);
        return max(left, right) + root -> val;
    }
    int maxPathSum(TreeNode* root) {
        pathSum(root);
        return ans;
    }
};

pathSum 函數代表以此節點為根的最大貢獻路徑長，每次遞迴包含以下過程：

  • 如果此點為空節點，返回 0。
  • 計算 left 為左子樹貢獻的最大長度，如果值為負數則直接捨棄 (路徑不包含左子樹)。
  • 計算 right 為右子樹貢獻的最大長度，如果值為負數則直接捨棄 (路徑不包含右子樹)。
  • 以此節點為根的最大路徑和為 left + right + root -> val，並且與當前最大值比較。
  • 回傳以此節點為根的最大貢獻路徑長，值為 max(left, right) + root -> val。

LeetCode 297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:
Input: root = []
Output: []

Solution:

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
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == nullptr) return "null";
        return to_string(root -> val) + " " + serialize(root -> left) + " " + serialize(root -> right);
    }
    TreeNode* dfs(queue<string>* q){
        string s = (*q).front();
        (*q).pop();
        if(s == "null") return nullptr;
        TreeNode* root = new TreeNode(stoi(s));
        root -> left = dfs(q);
        root -> right = dfs(q);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> q;
        stringstream ss(data);
        string tmp;
        while(ss >> tmp) q.push(tmp);
        return dfs(&q);
    }
};

  • 編碼
    使用前序遍歷，將二叉樹的值儲存為字串，如果遇到空節點，則加入 "null"。

  • 解碼
    使用queue 儲存每個字串，並且利用 dfs 將值依序填入根結點、左子樹、右子樹中。