# Leetcode刷題學習筆記--Tree Traversal
## Introduction
ref : [Tree Traversals (Inorder, Preorder and Postorder)](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)
1. pre-order
順序 : parent -> left -> right, 從top -> bottom
==適用於要先決定好parent才可以決定child。==
**1->2->4->5->3**
2. in-order
順序 : left child -> parent -> right child, 從bottom ->top
**4->2->5->1->3**
==在binary search tree(BST)中，使用inorder可以得到由小到大的排序。==
3. post-order
順序 : left child -> right child -> parent, 從bottom -> top
==適用於要先決定好child才可以決定parent==
**4->5->2->3->1**
4. level-order(BFS)
## Problems
### [653. Two Sum IV - Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)
給定一個target，找出在BST中是否有兩個node加起來為target。
想法:
1. 把node全部讀出來放入unordered_set
2. 如果不用額外的空間，只在tree中尋找。(下面code的解法)，這個也算是DFS的==pre-order==尋訪。如果是balanced binary tree則效率為O(logN)
```cpp=
TreeNode* findNode(TreeNode *root, int val) {
if(!root) return nullptr;
if(root->val == val) return root;
if(val > root->val) return findNode(root->right, val);
else return findNode(root->left, val);
}
bool helper(TreeNode* root, TreeNode* curr, int k) {
TreeNode* target;
if(!curr) return false;
target = findNode(root, k - curr->val);
if(target && target != curr)
return true;
else
return helper(root, curr->left, k) || helper(root, curr->right, k);
}
bool findTarget(TreeNode* root, int k) {
if(!root) return false;
return helper(root, root, k);
}
```
### [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)
給一個binary tree只輸出最右邊的value。典型的==level-order traversal==。
```cpp
void helper(vector<TreeNode *>& q, vector<int>& rtn) {
if(q.size() == 0) return;
vector<TreeNode *> newq;
for(TreeNode *node : q) {
if(node->left)
newq.push_back(node->left);
if(node->right)
newq.push_back(node->right);
}
rtn.push_back(q.back()->val);
helper(newq, rtn);
}
vector<int> rightSideView(TreeNode* root) {
if(!root) return {};
vector<int> rtn;
vector<TreeNode *> q;
if(root->left)
q.push_back(root->left);
if(root->right)
q.push_back(root->right);
rtn.push_back(root->val);
helper(q, rtn);
return rtn;
}
```
### [1008. Construct Binary Search Tree from Preorder Traversal(Medium)](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/)
給你一個用preorder排序過的vector，根據這個vector重建binary tree。
> 1. 第一個數值一定是root
> 2. 因為binary tree的特性是右邊的數值一定大於root，所以找出比第一個數值大的分界點。
> 3. 利用recursive來產生左右邊的sub-tree。
> ps: 可以用使只傳遞上下邊界來改善效能。
```cpp=
TreeNode* bstFromPreorder(vector<int>& preorder) {
auto n = preorder.size();
if(n == 0) return nullptr;
else if(n == 1) return new TreeNode(preorder[0]);
else {
auto pos = upper_bound(preorder.begin() + 1, preorder.end(), preorder[0]);
vector<int> left(preorder.begin() + 1, pos);
vector<int> right(pos, preorder.end());
return new TreeNode(preorder[0],
bstFromPreorder(left),
bstFromPreorder(right));
}
}
```
### [617. Merge Two Binary Trees(Easy)](https://leetcode.com/problems/merge-two-binary-trees/)
給你兩個binary tree, 如果位置一樣的node兩個tree都有，就把node的數值相加，不然就是取有的那個node。
> 1. 重複使用node，避免新增node。
> 2. 把數值都往root1加。
> 3. ==取root->left或root->right的時候，要先判斷root是否為null。==
```cpp=
TreeNode* helper(TreeNode *root1, TreeNode *root2) {
if(!root1 && !root2) return nullptr;
else if(!root1) return root2;
else if(!root2) return root1;
else {
root1->val += root2->val;
return root1;
}
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
TreeNode *newroot = helper(root1, root2);
if(newroot) {
newroot->left = mergeTrees(
root1 ? root1->left : nullptr,
root2 ? root2->left : nullptr);
newroot->right = mergeTrees(
root1 ? root1->right : nullptr,
root2 ? root2->right : nullptr);
}
return newroot;
}
```
### [1026. Maximum Difference Between Node and Ancestor(Medium)](https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/)
給你一個binary tree,找出任一node和parent最大的差值。
> 1. 不是一個BST，所以最大最小值不是最頂點的node。
> 2. ==因為差值是取abs，所以必須紀錄最大最小值。==
```cpp=
int helper(TreeNode *node, int maxv, int minv) {
if(!node) return -1;
int rtn = max(abs(maxv - node->val), abs(minv - node->val));
// 紀錄一路過來的最大最小值。因為差值是取abs
maxv = max(maxv, node->val);
minv = min(minv, node->val);
return max(rtn,
max(helper(node->left, maxv, minv),
helper(node->right, maxv, minv)));
}
int maxAncestorDiff(TreeNode* root) {
return max(helper(root->left, root->val, root->val),
helper(root->right, root->val, root->val));
}
```
### [572. Subtree of Another Tree(Easy)](https://leetcode.com/problems/subtree-of-another-tree/)
給你兩個binary tree(root, subRoot)，判斷root中是否有subtree和subRoot一樣。
> 1. 問題如果是問兩顆tree一不一樣，問題就簡單多了，只要用下面的isSameTree()來判斷。
> 2. 但是問題是問在root中的subtree，所以尋訪整個tree，如果第一的node數值一樣，就使用isSameTree()來判斷是不是一樣。
```cpp=
bool isSameTree(TreeNode *root, TreeNode *subRoot) {
if(!root && !subRoot) return true;
else if(!root || !subRoot) return false;
else {
if(root->val == subRoot->val)
return isSameTree(root->left, subRoot->left) &&
isSameTree(root->right, subRoot->right);
else
return false;
}
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!root) return false;
else if(isSameTree(root, subRoot))
return true;
else
return isSubtree(root->left, subRoot) ||
isSubtree(root->right, subRoot);
}
```
### [1022. Sum of Root To Leaf Binary Numbers(Easy)](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/)
給你一個binary，從root到leaf可以表示成一個binary數值，求出所有binary數值的和。
> 1. 所有進入helper()退出來的時候必須把原本加進去的數值退掉。
```cpp=
void helper(TreeNode *root, int& sum, int& cur) {
cur = (cur << 1) + root->val;
if(!root->left && !root->right) {
sum += cur;
return;
}
if(root->left) {
helper(root->left, sum, cur);
cur = cur >> 1;
}
if(root->right) {
helper(root->right, sum, cur);
cur = cur >> 1;
}
}
int sumRootToLeaf(TreeNode* root) {
int sum{0}, cur{0};
helper(root, sum, cur);
return sum;
}
```
### [236. Lowest Common Ancestor of a Binary Tree(Medium)](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)
給你一個binary tree和兩個node(p, q)。找出p, q共同最低的祖先node。
> 1. 如果root為共同的祖先，則可以在左半邊和右半邊找到p或q。
> 2. 如果root不為共同祖先，則只會在一邊找到p和q，另一邊找不到。那就往non-null的那邊繼續找。
```cpp=
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 找到p或q, return node
if(!root || root == p || root == q) return root;
// 左邊是否有p或q
TreeNode *left = lowestCommonAncestor(root->left, p, q);
// 右邊是否有p或q
TreeNode *right = lowestCommonAncestor(root->right, p, q);
// 左右邊都有，所以這是共同的root
if(left && right) return root;
// 否則選有的那一邊
return left ? left : right;
}
```
2022/07/05
> 1. 為什麼這題是使用post-order?
> 2. 因為我==必須先知道child的狀態==，才可以決定parent是不是LCA。
2024/02/09
還是參考了之前的解答。
```cpp=
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root == p || root == q) return root; // child狀態
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
// 得到兩邊child狀態之後再來判斷
if(l && r) return root;
else return l ? l : r;
}
```
### [968. Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/)
一台camera可以看到自己和上下的node，試問最少的camera可以覆蓋所有的node。
> 1. 一個node有三種狀態，放置camera，有被camera監視，沒有被camera監視。
> 2. 如果top-down，就必須考慮node的所有可能，還要根據root node狀態推斷child node可能的狀態，比較困難。
> 3. 如果bottom-up的話，因為bottom狀態確定了，比較容易推斷root node的狀態，所以使用bottom-up。
> 4. 既然是bottom-up，就是post-order，先走訪到最底部才開始判斷前一個的狀態。
```cpp=
class Solution {
enum state {mon, nomon, camera};
int cnt;
int helper(TreeNode *root) {
if(!root) return mon; // 把null node視為monitor node，因為不用管他
int l = helper(root->left);
int r = helper(root->right);
if(l == nomon || r == nomon) { // child有一個沒被monitor, 放置camera, case1
cnt++;
return camera;
} else if(l == mon && r == mon) // case2
return nomon;
return mon; // child 有一個有camera, case 3
// left, right
// mon, mon case 2, leaf
// mon, nomon case 1
// mon, camera case 3
// nomon, mon case 1
// nomon, nomon case 1
// nomon, camera case 1
// camera, mon case 3
// camera, nomon case 1
// camera, camera case 3
}
public:
int minCameraCover(TreeNode* root) {
int val = helper(root);
return (val == nomon ? 1 : 0) + cnt; // 因為root沒被monitor，所以放置一個camera
// time complexity : O(N)
// space complexity : O(N)
}
};
```
### [199. Binary Tree Right Side View(Medium)](https://leetcode.com/problems/binary-tree-right-side-view/)
列出一個binary tree每個level最右邊node的數值。
> 1. 使用preorder traversal，但是先走訪右邊再走訪左邊。因為我們想要先拿到右邊的node。
> 2. 使用level來記錄目前走到的level，因為每一層只有一個right-most node，所以當rtn.size() < level我們才紀錄。
```cpp=
class Solution {
void helper(TreeNode *root, int level, vector<int>& rtn) {
if(!root) return;
if(rtn.size() < level) rtn.push_back(root->val);
helper(root->right, level + 1, rtn);
helper(root->left, level + 1, rtn);
}
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> rtn;
helper(root, 1, rtn);
return rtn;
}
};
```
### [110. Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)
判斷binary tree是否為balanced。balanced的定義為從root來看左子樹和右子樹的高度差不為1。
> 1. 因為要先知道左右兩邊的高度，所以為post-order。
> 2. 得到兩邊子樹的高度之後，如果不是balanced那就不需要再判斷直接回傳-1。
> 3. 如果兩邊差大於1也是回傳-1。
> 4. 最後回傳計算後的高度。
```cpp=
int helper(TreeNode *root) {
if(!root) return 0;
int hofl = helper(root->left);
int hofr = helper(root->right);
if(hofl == -1 || hofr == -1 || abs(hofl - hofr) > 1) return -1;
return max(hofl, hofr) + 1;
}
bool isBalanced(TreeNode* root) {
return helper(root) == -1 ? false : true;
}
```
### [437. Path Sum III](https://leetcode.com/problems/path-sum-iii/)
找到在binary tree中的path剛好總合為target。這邊的path的定義是從parent到child。不會有child->parent->child的路徑。
> 1. 每個node都可以為起始點，所以使用line 13, line 14，把path總和算是每個node的起點。
> 2. 使用helper來計算以root為起點的path總和。
> 3. 在helper中經過的每個node都為終點，所以計算總合。line 3。
> 4. 如果以這個點的總和為target則加1，line 4。
> 5. 繼續統計以root->left和root->right為終點的path。line 5,6。
> 6. 因為有line 13, 14，所以不必計算單點是否等於target。
```cpp=
int helper(TreeNode *root, long pre) {
if(!root) return 0;
long cur = pre + root->val;
return (cur == target) +
helper(root->left, cur) +
helper(root->right, cur);
}
int target;
int pathSum(TreeNode* root, int targetSum) {
if(!root) return 0;
target = targetSum;
return helper(root, 0) +
pathSum(root->left, targetSum) + // 從 root->left開始，所以不用判斷每個點是否為traget
pathSum(root->right, targetSum); // 從 root->right開始
}
```
### [2246. Longest Path With Different Adjacent Characters](https://leetcode.com/problems/longest-path-with-different-adjacent-characters/description/)
找出tree中，最長的path其中每兩個相鄰的node的char都不一樣。
> 1. 一開始使用了DFS結果TLE。
> 2. 參考了lee215大的解法，發現這題和[124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)蠻像的。
> 3. 應該說只要是在tree中找path應該都是一樣的套路。
> 4. path至少會有一個node，
> 5. 兩個以上的node就是會跟child連在一起。
> 6. 有可能跟一個child連在一起，也有可能跟兩個child連在一起。
> 7. 如果是跟兩個child連在一起。那一定是最長的兩個child。
> 8. why preorder? 因為必須先知道每個child最長的path。
> 9. 根據s[cur] != s[child]，才可以判斷要不要取用這條path。所以判斷必須在pre-order之後。
> 10. 回傳只能傳回node + 最長的child。
```cpp
class Solution {
// why pre-order?
// 因為必須先知道每個child的最長path，
// 根據s[cur] != s[child]，才可以判斷可不可以取用這條path，
// 必須取出兩條最長的child path就可以拼成更長的Path
int maxans{0};
int dfs(unordered_map<int, vector<int>>& m, int cur, string& s, int len) {
int big1{0}, big2{0};
for(auto& child : m[cur]) {
int rtn = dfs(m, child, s, len + 1); // 從目前node往下的path長度
if(s[cur] == s[child]) continue;
if(rtn > big2) big2 = rtn;
if(big2 > big1) swap(big1, big2);
}
maxans = max(maxans, big1 + big2 + 1); // 經過node最長的path由node和兩個最長的邊組成
return big1 + 1; // 最長一條path
}
public:
int longestPath(vector<int>& parent, string s) {
unordered_map<int, vector<int>> m; // node, adj node
for(int i = 1; i < parent.size(); ++i)
m[parent[i]].push_back(i);
dfs(m, 0, s, 0);
return maxans;
}
};
```
### [958. Check Completeness of a Binary Tree](https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/)
給你一個TreeNode* root，試判斷是否為complete binary tree。
> 1. 一開始一直在想到底是要用pre-order, in-order或是post-order，就是忘了想用level order。
> 2. 另一個解法是把每個node都給上一個value，最後排序這個vector但是會int overflow。
> 3. 根據 complete binary tree的特性，如果我用level order traversal，就不會在node之前先遇到nullptr。
> 4. 如果是complete binary tree最後的queue內容都會是nullptr。
```cpp=
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> q{{root}};
// 遇到nullptr就停止。
while(q.front() != nullptr) {
TreeNode* cur = q.front(); q.pop();
q.push(cur->left);
q.push(cur->right);
}
// 如果是complete binary tree的話，最後都會是nullptr
while(!q.empty() && q.front() == nullptr) q.pop();
return q.empty();
}
```
### [979. Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/description/)
binary tree中每個node都有不同的coins，找出最少的移動可以使每個node都有一個coin。
> 1. 參考官方解答。
> 2. why post-order traversal?
> + 必須知道需要往child移動多少的coins，或是必須知道要從child移動多少coins上來parent。
> + 正數表示child有多的coins必須移動上來。
> + 負數表示child有少，必須從parent動到child。
> 3. 因為child移動到child都要經過parent，所以可以視為多的先從child移動到parent，parent再分配給child。
> 4. 也就是parent是一個中央統籌單位，多的coins先交給中央parent，再由中央parent分配給不夠的child。
> 5. 如果整體來說還是不夠，中央parent再跟更上面的parent要求更多的coins。
> 6. 如果分配完了還有多出來，中央parent再把剩下的往更上的parent繳交出去。
```cpp=
class Solution {
int ans{};
// child多的coin，必須從child移動到root
// child缺的coin, 必須從root移動到child
int dfs(TreeNode* root) { // + : child->root, - : root->child
if(!root) return 0;
int l = dfs(root->left);
int r = dfs(root->right);
ans += abs(l) + abs(r);
return root->val + l + r - 1;
}
public:
int distributeCoins(TreeNode* root) {
dfs(root);
return ans;
}
};
```
### [2477. Minimum Fuel Cost to Report To the Capital](https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/description/)
每個node除了0之外，都要往node 0前進，每前進一個node需要1L fuel。一台車子最多有seats個椅子。試問，最少的fuel來讓所有的node都達到node 0。
> 1. 如果有n個人，則需要多少台車子? 使用無條件進位ceil。
```cpp
ceil(n / s);
```
> 2. 所以使用post-order，因為要到達最後的leaf node，再往node 0前進，推算有多少個node在後面。
> 3. 使用vector<int> vis來記錄訪問過的node。
> 4. 為什麼統計每個node的車子數，就是統計需要的fuel?
```cpp=
class Solution {
unordered_map<int, vector<int>> adj;
vector<int> vis; // 使用visited array來避免重複走
long long ans;
int dfs(int n, int s) {
vis[n] = 1;
int count = 1;
//統計從child過來的node有多少個
for(auto& nxt : adj[n]) {
if(!vis[nxt])
count += dfs(nxt, s);
}
if(n != 0)
ans += ceil((double)count / s); //站在每個node，會有幾台車經過
// ans += ((rtn + seats - 1) / seats);
// 不使用ceil的無條件進位
return count; // 有多少個node
}
public:
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
for(auto& r : roads) {
adj[r[0]].push_back(r[1]);
adj[r[1]].push_back(r[0]);
}
vis.resize(roads.size() + 1);
dfs(0, seats);
return ans;
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
Connect another wallet