Binary Tree Inorder Traversal — leetcode

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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » Binary Tree Inorder Traversal — leetcode

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡