---
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)的問題)
```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`
Sign in with Wallet
Connect another wallet