Created
August 13, 2014 06:32
-
-
Save xiren-wang/a8ecca4f6039c9b6c100 to your computer and use it in GitHub Desktop.
Binary Tree Inorder Traversal, iterative solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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? | |
*/ | |
/** | |
* 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) { | |
//for root | |
// push rightChild to stack | |
// push root (indicated that it's visited) to stack | |
// push leftChild to stack | |
// then while !stack.empty | |
// if topEle visited before, output its value | |
// else, push its right, itself(mark visited), its left | |
// How does it work: | |
// if an element was popped and visited, it must be the root of some subtree | |
// since its left children tree was popped out already, then this root should be output | |
// | |
stack<TreeNode *> myS; | |
unordered_set<TreeNode *> visited; | |
vector<int> vInt; | |
if (!root) | |
return vInt; | |
if (root->right) | |
myS.push(root->right); | |
myS.push(root); visited.insert(root); | |
if (root->left) | |
myS.push(root->left); | |
//working with stack | |
while (!myS.empty()) { | |
TreeNode *topEle = myS.top(); myS.pop(); | |
//if previous pushed as root, output data | |
if (visited.find(topEle) != visited.end()) { | |
vInt.push_back(topEle->val); | |
visited.erase(topEle); //not be used again, save memory | |
} | |
else { //not pushed as root, now push right, itself(marked), left | |
if (topEle->right) | |
myS.push(topEle->right); | |
myS.push(topEle); visited.insert(topEle); | |
if (topEle->left) | |
myS.push(topEle->left); | |
} | |
} | |
return vInt; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment