Binary Tree Inorder Traversal -- leetcode
來源：程序員人生 發布時間：2015-05-07 09:28:52 閱讀次數：2953次
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
實現中序遍歷，且不能用遞歸。
算法1：使用棧
中序遍歷為，先訪問左子樹，再訪問根。
訪問完左子樹，需要要回到根。而樹本身并沒有存儲到根的指針。
故需要棧的幫助，存儲指向父結點的指針。即先把自己入棧，再進入左子樹。
此代碼在leetcode上，實際履行時間為5ms。
/**
* Definition for binary tree
* 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> ans;
stack<TreeNode *> s;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};
以上代碼，也能夠寫作：
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
stack<TreeNode *> s;
while (!s.empty() || root) {
if (root) {
s.push(root);
root = root->left;
}
else {
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
}
return ans;
}
算法2
Morris Traversal
利用空閑的right指針指向根結點。這樣在訪問完左子樹時，根據右孩子，回到根結點。
中序遍歷，要求，先訪問左子樹的所有結點，然后訪問該結點。
那末根結點root的左子樹中最右下的結點rightMost必為左子樹最后1個被訪問的結點。而此結點rightMost的右指針，必為空。 則可以復用此右指針，指向根結點root。 這樣，在訪問完rightMost后，就能夠回到根結點root了。
故，在進入左子樹之前，先找到左子樹中最右下的結點，讓其right指針，指向自己。未思進，先思退。留好退路。
這樣，rigth指針就有2義性，即表示右子樹，又表示先人結點。如何避免2義性呢，同時也為了不死循環。
那就是，在尋覓其左子樹的最右下結點時，如果又回到了自己。說明它左子樹，已全部訪問完成。
即，尋覓最右結點時，會出現兩種情況，1種是碰到right為空；1種是回到了自己。
此代碼在leetcode上實際履行時間為4ms。
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
while (root) {
if (!root->left) {
ans.push_back(root->val);
root = root->right;
}
else {
TreeNode *rightMost = root->left;
while (rightMost->right && rightMost->right != root)
rightMost = rightMost->right;
if (!rightMost->right) {
rightMost->right = root;
root = root->left;
}
else {
ans.push_back(root->val);
rightMost->right = 0;
root = root->right;
}
}
}
return ans;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
