正如題目Binary Tree Inorder Traversal，本題便是實作中序走訪。
在這裡，共有四種實作方式：
1.
Recursion 遞迴：時間複雜度O(n) ，空間複雜度O(n)
(1)
最直覺而簡單易懂的實作方式，依左子樹、根、右子樹之順序遞迴呼叫自己。
(2)
但缺點是遞迴受限於二元樹之階層數，有記憶體空間利用上的缺陷。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
in_tra(root, &result);
return result;
}
void in_tra(TreeNode* node, vector<int>* result){
if(!node) return;
in_tra(node->left, result);
(*result).push_back(node->val);
in_tra(node->right, result);
}
};
2.
Stack & Map 堆疊與映射：時間複雜度O(n) ，空間複雜度O(n)
(1)
建立一TreeNode指標(TreeNode*)型態之Stack與Map(TreeNode*→bool)。
(2)
Stack是為了實作出遞迴，而Map是為了記憶走訪過之節點。
(3)
流程解說：
l
確認「Stack不為空」後進入while迴圈：(在開始之前已將根節點root推入Stack)
n
先將Stack頂層元素指定給currNode，再進行分支判斷。
n
分支判斷一(if)：「currNode之左元素不為空」且「Map中對映currNode之布林值為false」
u 將currNodee之左元素推入Stack。
u 將Map中對映currNode之布林值改為true。
n
分支判斷二(else)：
u 將currNode值推入回傳結果陣列(result)。
u 移除Stack頂端元素(就是現在的currNode，未來不再走訪)。
u 分支判斷：「currNode之右元素不為NULL」
² 將currNode之右元素推入Stack。
l
繼續重複while迴圈，直到退出並回傳結果陣列(result)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if(!root) return result;
unordered_map<TreeNode*, bool> map;
vector<TreeNode*> stack;
stack.push_back(root);
TreeNode *currNode;
while(!stack.empty()){
currNode = stack.back();
if(currNode->left && !map[currNode]){
stack.push_back(currNode->left);
map[currNode] = true;
}
else{
result.push_back(currNode->val);
stack.pop_back();
if(currNode->right){
stack.push_back(currNode->right);
}
}
}
return result;
}
};
3.
Pure Stack 純堆疊：時間複雜度O(n)，空間複雜度O(n)
(1)
這個方式是由上一個演算法修改而來，並在保留Stack的基礎上，新增了兩個變數：currNode與preNode(皆為TreeNode*型態)。
(2)
currNode意指「正在走訪的節點」，而preNode意指「currNode的上一個節點」。
(3)
流程解說：
l
確認「Stack不為空」或「currNode不為空」後進入while迴圈：(在開始之前將currNode設為根節點root)
n
分支判斷一(if)：「currNode不為空」
u 將currNode推入Stack。
u 將currNode指向currNode之左元素。
n
分支判斷二(else)：
u 將Stack頂層元素指定給preNode。
u 將preNode值推入回傳結果陣列(result)。
u 移除Stack頂端元素(就是現在的preNode，未來不會再走訪)。
u 將currNode指向preNode之右元素。
l
繼續重複迴圈，直到退出並回傳結果陣列(result)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
vector<TreeNode*> stack;
TreeNode *currNode = root;
TreeNode *preNode;
while(!stack.empty() || currNode){
if(currNode){
stack.push_back(currNode);
currNode = currNode->left;
}
else{
preNode = stack.back();
result.push_back(preNode->val);
stack.pop_back();
currNode = preNode->right;
}
}
return result;
}
};
4.
Morris Traversal 莫里斯走訪：時間複雜度O(n)，空間複雜度O(1)
(1)
這個演算法實作出的中序走訪不需要Stack，也因此空間複雜度為O(1)。
(2)
這個演算法不會破壞原二元樹形狀。(中間過程有變形)
(3)
使用「引線二元樹」的概念(threaded binary tree)，令元素的左右指標指向上一個或下一個節點，以此在缺少Stack的情況下實作出從子節點走訪回父節點的方式。
(4)
currNode意指「正在走訪的節點」，而preNode意指「currNode的上一個節點」。
(5)
流程解說：
l
確認「currNode不為空」後進入while迴圈：(在開始之前將currNode設為根節點root)
n
分支判斷一(if)：「currNode之左元素不為空」(在現在的左子樹底下找到preNode)
u 將preNode指向currNode之左元素。
u while迴圈：「preNode之右元素不為空」且「preNode之右元素不為currNodee」
² 將preNode指向preNode之右元素。(此為preNode)
u 分支判斷一(if)：「preNode之右元素為空」(改變樹的形狀)
² 將preNode之右元素指向currNode。
² 將currNode指向currNode之左元素。(繼續走訪下一個元素)
u 分支判斷一(else)：「preNode之右元素不為空」(回復樹的形狀)
² 將preNode之右元素指向NULL。
² 將currNode值推入回傳結果陣列(result)。
² 將currNode指向currNode之右元素。(繼續走訪下一個元素)
n
分支判斷二(else)：
u 將currNode值推入回傳結果陣列(result)。
u 將currNode指向currNode之右元素。(繼續走訪下一個元素)
l
繼續重複迴圈，直到退出並回傳結果陣列(result)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
TreeNode* currNode = root;
TreeNode* preNode;
while(currNode){
if(currNode->left){
preNode = currNode->left;
while(preNode->right && (preNode->right)!=currNode)
preNode = preNode->right;
if(!(preNode->right)){
preNode->right = currNode;
curNode = currNode->left;
}
else{
preNode->right = NULL;
result.push_back(curNode->val);
curNode = curNode->right;
}
}
else{
result.push_back(curNode->val);
curNode = curNode->right;
}
}
return result;
}
};
留言
張貼留言