Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
解題思路:
遞歸版：
class Solution {
public:
void getPreorderData(TreeNode* root,vector<int> & ret)
{
if(root == NULL) return;
ret.push_back(root->val);
if(root->left) getPreorderData(root->left,ret);
if(root->right) getPreorderData(root->right,ret);
return;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
getPreorderData(root,ret);
return ret;
}
};
迭代版：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode *> stk;
TreeNode* curr = root;
while(curr)
{
ret.push_back(curr->val);
if(curr->right)
stk.push(curr->right);
curr = curr->left;
if(curr == NULL && !stk.empty())
{
curr = stk.top();
stk.pop();
}
}
return ret;
}
};
參考資料：https://discuss.leetcode.com/topic/6493/accepted-iterative-solution-in-java-using-stack
