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?
这题简单,属于课本习题的难度,题目提示说用迭代试试,当然用递归也可以AC的。迭代的时候要注意栈的性质,不要push反了。
void preorderIter2(TreeNode *node, stack<TreeNode*>&st, vector<int>&ret) {
while (!st.empty()) {
TreeNode *top = st.top();
st.pop(); ret.push_back(top->val);
if (top->right) st.push(top->right);
if (top->left) st.push(top->left);
}
} vector<int> preorderTraversal(TreeNode *root) {
vector<int> ret;
if (!root) return ret;
stack<TreeNode *> st;
st.push(root);
preorderIter2(root, st, ret);
return ret;
}
迭代版
void preorderIter(TreeNode *node, vector<int> &ret) {
if (!node) return;
ret.push_back(node->val);
cout << node->val <<endl;
preorderIter(node->left, ret);
preorderIter(node->right, ret);
}
迭代