Description:
Achieve binary tree tranversal in O(1) space and O(n) time.
解题方法：
For the current node:
- If it doesn't have left child, print out and go to the right child.
- Ohterwise, find out the most right leaf in its left child tree. Then, if this
mostRightLeaf->right == currnode, print out and go to the right child; Or, makemostRightLeaf->right = curr, then go to the left child. - Repeat step 1 and 2, untill
curr == NULL;
Time Complexity：
time: O(n)
space: O(1)
完整代码：
Inorder:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if(!root)
return result;
TreeNode* curr = root;
while(curr) {
TreeNode* mostRight = NULL;
if(curr->left) {
mostRight = findMostRight(curr, curr->left);
}
if(!mostRight || (mostRight && mostRight->right == curr)) {
cout<<curr->val<<endl;
result.push_back(curr->val);
curr = curr->right;
} else {
mostRight->right = curr;
curr = curr->left;
}
}
return result;
}
TreeNode* findMostRight(TreeNode* prev, TreeNode* root) {
if(!root)
return NULL;
while(root->right && root->right != prev) {
root = root->right;
}
return root;
}
