For example:
Given binary tree
{1,#,2,3}
,
1 \ 2 / 3return
[1,2,3]
.
Note: Recursive solution is trivial, could you do it iteratively?
Solution: when it comes to the binary tree traversal, we need a stack if the node in the tree has no parent pointer. The idea of the solution 1 is quite simple and I found it online:
- Push the root into stack;
- Do the follwoing steps until the stack is empty:
- Pop out the top-most node in the stack as the current node; and print it;
- Push its right child and then left child into stack if they exist.
/*******************************SOLUTION 1***********************************/
/** * 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> preorderTraversal(TreeNode *root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<int> ret; if(root==NULL) return ret; stack<TreeNode*> st; st.push(root); while(!st.empty()){ TreeNode* cur = st.top(); st.pop(); ret.push_back(cur->val); //or print it on the fly if(cur->right!=NULL) st.push(cur->right); if(cur->left!=NULL) st.push(cur->left); } return ret; } };/*******************************SOLUTION 2***********************************/
/** * 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> preorderTraversal(TreeNode *root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<int> ret; if(root==NULL) return ret; stack<TreeNode*> st; TreeNode* cur = root; do{ ret.push_back(cur->val); if(cur->left==NULL && cur->right==NULL){ if(!st.empty()){ cur=st.top()->right; st.pop(); } else cur=NULL; } else if(cur->left!=NULL && cur->right!=NULL){ st.push(cur); cur=cur->left; } else if(cur->left!=NULL) cur=cur->left; else cur=cur->right; }while(!st.empty() || cur!=NULL); return ret; } };
No comments:
Post a Comment