problem:
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?
Hide Tags Tree Stack 题意:非递归前序遍历二叉树
thinking:
(1)前序遍历的递归法很easy,本题要求非递归,借助stack实现
(2)思路是:不为空时,优先将节点的左孩子入栈,入栈时即访问节点值,如果左孩子为空,取栈顶节点,访问其右孩子,再重复上述步奏。
code:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode *> _stack;
TreeNode *node = root;
while(node!=NULL ||!_stack.empty())
{
if(node!=NULL)
{
ret.push_back(node->val);
_stack.push(node);
node=node->left;
}
else
{
node=_stack.top();
_stack.pop();
node=node->right;
}
}
return ret;
}
};