---
# System prepended metadata

title: 題解：二元樹 Binary Tree
tags: [solution]

---

---
title: 題解：二元樹 Binary Tree
tags: solution
---


# [LeetCode] 700. Search in a Binary Search Tree
- 題目連結：[700. Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/)

輸入已經是一棵建好的二元搜尋樹，故只需要進行尋訪即可，
可以用迴圈來跑，亦或是用遞迴來跑。

> <font color=red>> 補充：堆疊溢位(stack overflow)</font>
> 只以單一路徑遍歷二元樹的時候，並不建議使用遞迴來跑，
> 若遞迴過深，則有可能會引發「堆疊溢位 stack overflow」
> 
> 二分搜尋樹如何引發遞迴過深的錯誤?
> 如果這樣輸入：1 2 3 4 5 6 ... 1000000
> (這種情況又被稱為worst case)
>
> Wiki介紹 : [堆疊溢位](https://zh.wikipedia.org/wiki/%E5%A0%86%E7%96%8A%E6%BA%A2%E4%BD%8D)
> (在其他線上程式評測區或是程式競賽使用的時候，通常都不會有堆疊溢位的問題)

```cpp=
TreeNode* searchBST(TreeNode* root, int val) {
    while(root != nullptr && root->val != val)
        root = (root->val < val) ? root->right : root->left;

    return root;
}
```
> Judgment Status : AC (36ms, 34.7MB)
---

# [LeetCode] 104. Maximum Depth of Binary Tree
- 題目連結：[104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

Let $h(x)$ is the max-depth of the binary tree at the node $x$,
we can write as the simple recursion:


$h(x)=
\begin{cases}
0 & \text{if x is null}\\
1+\text{max}(h(x_{\text{left}}),\text{ }h(x_{\text{right}})) & \text{if x isn't null}
\end{cases}$
```cpp=
int maxDepth(TreeNode* root) {
    if(root == nullptr)
        return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
```
> Judgment Status : AC (0ms, 18.7MB)
---

# [LeetCode] 938. Range Sum of BST
- 題目連結：[938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)

$f(x)=\begin{cases}
0 &\text{if } x=\text{null} \\
f(x_{\text{left}}) + f(x_{\text{right}}) + x_{\text{val}} & \text{if }x_{\text{val}} \in[\text{low, high}] \\
f(x_{\text{left}}) + f(x_{\text{right}}) & \text{if }x_{\text{val}} ∉[\text{low, high}] \\
\end{cases}$

```cpp=
int rangeSumBST(TreeNode* root, int low, int high) {
    if(root == nullptr)
        return 0;

    return rangeSumBST(root->left,low,high) + 
           rangeSumBST(root->right,low,high) +
           ((low <= root->val && root->val <= high) ? root->val : 0);
    }

```
> Judgment Status : AC (120ms, 64.7MB)
---

# [LeetCode] 965. Univalued Binary Tree
- 題目連結：[965. Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)

$f(x)=\begin{cases}
\text{T}_0 & \text{if }x\text{ is null}\\
\text{F}_0 & \text{if }x_{\text{val}}\neq \text{univalue}\\
f(x_{\text{left}}) ∧ f(x_{\text{right}}) & \text{if }x_{\text{val}}= \text{univalue}
\end{cases}$

(∧ is AND mathmetical logical operator)

```cpp=
int univalue;

bool check(TreeNode* root) {
    if(root == nullptr)
        return true;

    if(root->val != univalue)
        return false;

    return check(root->right) && check(root->left);
}

bool isUnivalTree(TreeNode* root) {
    univalue = root->val;
    return check(root);
}
```
> Judgment Status : AC (0ms, 9.8MB)








---

# [程式自學平台] C_DT43-易 - 嚴格二元樹
- 題目連結：[[C_DT43-易] 嚴格二元樹](https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=21770)

檢查Strictly/Full Tree的方式：左右節點有空，且兩個節點非全空時，此樹非嚴格二元樹

```cpp=
# include <iostream>
using namespace std;

// the node structure of Binary Tree, stored value, depth, left and right child
struct Node{
    int val, depth;
    Node *left, *right;

    Node(int v, int h){
        val = v, depth = h;
        left = right = nullptr;
    }
};

// examine the tree is a strictly binary tree or not
bool is_strictly(Node *node){
    if(node == nullptr || (node->left == nullptr && node->right == nullptr))
        return true;

    if(node->left == nullptr || node->right == nullptr)
        return false;

    return is_strictly(node->left) && is_strictly(node->right);
}

int main(){

    int N,n;
    Node *root, *cur;
    int height = 1;

    cin>>N>>n;
    root = new Node(n,1);


    while(--N){
        cin>>n;
        cur = root;

        // binary searching
        while(true){
        
            // if the value to be inserted is greater than the current node's value
            if(n > cur->val){

                // move to the right child
                if (cur->right == nullptr){
                    cur->right = new Node(n,cur->depth+1);
                    height = max(height,cur->depth+1);
                    break;
                }
                cur = cur->right;
            }
            
            else{
                if(cur->left == nullptr){
                    cur->left = new Node(n,cur->depth+1);
                    height = max(height,cur->depth+1);
                    break;
                }
                cur = cur->left;
            }
        }
    }
    
    cout<<(is_strictly(root) ? "True" : "False")<<' '<<height<<'\n';
}
```
> Judgment Status : AC (28ms, 0KB)

---

# [LeetCode] 102. Binary Tree Level Order Traversal
- 題目連結：[102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

以下是變數的用途：
 - **cur_level** : 紀錄當前層的數量(current level amount)
 - **next_level** : 記錄下一層的數量(next level amount)
 - **depth** : 樹深度，用來記錄二維陣列的高度
 - **buf** : BFS的暫存佇列(buffering queue)，在這裡使用deque來開，但其實僅使用了queue的功能
 - **result** : 二維陣列，用來存BFS的遍歷結果

在進入BFS之前，會先在buf裡面存入第一個節點，以及會將cur_level設為1 
(第一層只會有一個節點，也就是root)

這裡紀錄是否要切換到下一層的方式是：當cur_level的數量歸零時，即要切換至下一層。
(參考程式碼 line: 29~39 的部分)




```cpp=
vector<vector<int>> levelOrder(TreeNode* root) {

    // ----- declaring variables -----
    int next_level = 0, cur_level = 1;
    int depth = 0;
    deque<TreeNode*> buf;
    vector<vector<int>> result;
    
    if(root == nullptr)    //special case : if nothing
        return result;

    // ----- initializing -----
    result.push_back(*(new vector<int>));
    buf.push_back(root);


    // ----- BFS -----
    while(!buf.empty()){    // when BFS buffer is not empty
    
        // storing result
        result[depth].push_back(buf.front()->val);

        // add right-child & left-child to buffer
        if(buf.front()->left != nullptr)
            buf.push_back(buf.front()->left), next_level++;
        if(buf.front()->right != nullptr)
            buf.push_back(buf.front()->right), next_level++;

        // if current level amount is 0, goto next level
        if(--cur_level <= 0){
            cur_level = next_level;
            
            // if next level existed
            if(cur_level){
                result.push_back(*(new vector<int>));
                depth++;
            }
            next_level = 0;
        }
        
        // remove current node from buffer
        buf.pop_front();
    }
    // ----- BFS end -----
    
    return result;
}
```
> Judgment Status : AC (0ms, 12.5MB)

---

# [程式自學平台] C_DT26-中 - 樹的走訪方式
- 題目連結：[[C_DT26-中] 樹的走訪方式](https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=13741)

以下是變數的用途：

**buf** : BFS時用來儲存根的佇列 (可以把它看成是一個暫存器)
**nodes** : 全部欲要放進來的節點 (把它存成佇列，是因為input的順序是BFS時的順序)
**head** : 整個二元樹的頭
**root** : 用來儲存buf的第一個指標，當作根來用 (~~為了減少程式碼長度~~)

有關於建樹的一個簡單思路：

取出二元樹的head，並把剩下全部的節點到nodes的佇列裡，
將head放入buffer中，以BFS的方式來建樹。


```cpp=
# include <iostream>
# include <deque>

using namespace std;

// ----- Binary Tree structure ------
struct Node{
    int val;
    Node *left, *right;
    bool l, r;            // have left, right

    Node(int v, bool a, bool b){
        val = v;
        l = a, r = b;
        left = right = nullptr;
    }
};

// ----- DFS -----
void DFS(Node *node){
    if(node == nullptr)
        return;

    cout<<' '<<node->val;
    DFS(node->left);
    DFS(node->right);
}

int main(){
    int v;
    bool l,r;
    deque<Node*> buf;
    deque<Node*> nodes;
    Node* head;
    Node* root;

    // ----- initializing -----
    cin>>v>>l>>r;
    head = new Node(v,l,r);    // start with head
    buf.push_back(head);


    // ---- input all node -----
    while(cin>>v>>l>>r)
        nodes.push_back(new Node(v,l,r));


    // ----- BFS spaning tree -----
    while(!nodes.empty() && !buf.empty()){
        root = buf.front();
        buf.pop_front();

        // ----- distributing nodes to root -----
        if(root->l){
            root->left = nodes.front();
            nodes.pop_front();
        }
        if(root->r){
            root->right = nodes.front();
            nodes.pop_front();
        }

        // ----- move root to next(left & right) -----
        if(root->left != nullptr)
            buf.push_back(root->left);

        if(root->right != nullptr)
            buf.push_back(root->right);
    }

    cout<<head->val;
    DFS(head->left);
    DFS(head->right);
    cout<<'\n';
}
```
> Judgment Status : AC (27ms, 0KB)

### - [C_DT26-中] 樹的走訪方式：簡化版程式碼

~~以下曬程式碼~~ (以下的程式碼和思路解說看不太懂的話，請不用太擔心(#
1. 使用「一維陣列建構二元樹」，可以省去非常多處理節點的步驟 (直接省去寫一個struct的步驟)。
2. 使用普通的陣列(搭配begin和end)來取代deque。
3. 邊讀邊做
4. 下面將判定一個節點是否有左和右節點，用位元的方式存起來，表示成：$(l<<1)+r$ 
    若 $((l<<1)+r)\&2$ 則有左節點，並在buffer後面加入 $(x<<1)$ 的節點
    若 $((l<<1)+r)\&1$ 則有右節點，並在buffer後面加入 $(x<<1)+1$ 的節點

> <font color=red>>>！請注意！<<</font>
> <font color=black>**「位元運算 Bitwise Operations」**</font>與離散的<font color=black>**「邏輯運算 Logical Operations」**</font>
> 這兩個是不同的數學運算方式，請千萬別把這兩個東西給混淆了！
> 如果你不知道位元運算是什麼，可以參考之前的筆記：[快速冪(上) - 前導：位元運算子](https://hackmd.io/@cycu2021cs-group/rki6_relO#%E5%89%8D%E5%B0%8E%EF%BC%9A%E4%BD%8D%E5%85%83%E9%81%8B%E7%AE%97%E5%AD%90Bitwise-operator)

> <font color=black>(補充資料)</font>
> pair是一個資料結構，其可以存兩個指定型態的變數(這兩個型態可不同)，
> 宣告使用`pair<T1><T2>` ，替換T1,T2為指定型態，其名Template
>
> [pair - C++ Reference](http://www.cplusplus.com/reference/utility/pair/)
> [C++ pair的基本用法总结（整理）](https://blog.csdn.net/sevenjoin/article/details/81937695)
> 
> [GeeksforGeeks : Templates in C++](https://www.geeksforgeeks.org/templates-cpp/)

```cpp=
# include <iostream>
using namespace std;

pair<int,int> bt[10000];    // binary tree

void DFS(const int i){
    if(!bt[i].first)
        return;

    cout<<' '<<bt[i].first;
    DFS(i<<1);
    DFS((i<<1)+1);
}

int main(){

    int v,x,l,r;
    int buf[1000], buf_begin = 0, buf_end = 0;
    
    cin>>v>>l>>r;
    bt[1] = make_pair(v,(l<<1)+r);
    buf[buf_end++] = 1;

    while(buf_begin < buf_end){
        if(bt[x = buf[buf_begin++]].second & 2){
            cin>>v>>l>>r;
            bt[buf[buf_end++] = x<<1] = make_pair(v,(l<<1)+r);
        }
        if(bt[x].second & 1){
            cin>>v>>l>>r;
            bt[buf[buf_end++] = (x<<1)+1] = make_pair(v,(l<<1)+r);
        }
    }

    cout<<bt[1].first;
    DFS(2);
    DFS(3);
    cout<<'\n';
}
```
> Judgment Status : AC (28ms, 0KB)
> (開啟IO加速後，其速度比上方的指標建樹版還來的慢，這點我也不是很清楚是為什麼)


---

# [ZeroJudge] d453.  最短距離
- 題目連結：[d453: 最短距離](https://zerojudge.tw/ShowProblem?problemid=d453)

用BFS解題的思路是這樣的：
1. 由當前位置，往上、下、左、右四個方向進行遍歷，直到遇到終點為止
2. 走過的道路不能再被走過，可以把走過的道路用牆壁給封死
   (若有路線會走到重複走過的路線上，那就絕對不會是最短路徑)

在建二維陣列的時候，可以將外圈用牆壁包住(外圈全部填1)，
此迷宮的左上角位置會變成是(1,1)，而不是(0,0)，因為(0,0)已經是牆壁了。
(題目輸入的左上角座標也是(1,1)，剛好不需要去在意起點是(0,0)的問題)

![](https://i.imgur.com/HZaZWAY.png =130x)



```cpp=
# include <iostream>
# include <deque>
using namespace std;

char maze[105][105];

struct pos{
    int x, y;
    int steps;

    pos(int a, int b, int s){
        x = a, y = b, steps = s;
    }
};

int main(){
    int T,N,M,x,y,s;
    int end_x, end_y;


    cin>>T;
    while(T--){
        deque<pos> buf;

        // ------------- input -------------
        cin>>N>>M;
        cin>>x>>y>>end_x>>end_y;


        // --------- initializing ----------
        buf.push_back(pos(x,y,1));


        // -------- building border --------
        for(x = 0 ; x<=N+1 ; x++)
            maze[x][0] = maze[x][M+1] = '1';
        for(y = 0 ; y<=M+1 ; y++)
            maze[0][y] = maze[N+1][y] = '1';


        // ---------- input maze ----------
        for(x = 1 ; x<=N ; x++)
            for(y = 1 ; y<=M ; y++)
                cin>>maze[x][y];


        // -------------- BFS --------------
        while(!buf.empty()){
            x = buf.front().x, y = buf.front().y, s = buf.front().steps;

            if(x == end_x && y == end_y)    // arrived destination
                break;

            if(maze[x-1][y] == '0')
                buf.push_back(pos(x-1,y,s+1)); // up

            if(maze[x+1][y] == '0')
                buf.push_back(pos(x+1,y,s+1)); // down

            if(maze[x][y-1] == '0')
                buf.push_back(pos(x,y-1,s+1)); // left

            if(maze[x][y+1] == '0')
                buf.push_back(pos(x,y+1,s+1)); // right

            maze[x][y] = '1';    // block the road walked
            buf.pop_front();

        }
        // ------------ BFS end ------------
        
        if(buf.empty())
            cout<<"0\n";
        else
            cout<<s<<'\n';

    }
}
```

> Judgment Status : AC (3ms, 344KB)

###### posted date: `2021.4.17` 