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