144 Binary Tree Preorder Traversal
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?
- A stack will naturally preserve the pre-order, in a very similiar way that level order used a queue. A stack will prioritize elements that come from the left FIRST, before the right.
// iteratively
vector<int> preorderTraversal(TreeNode* root) {
vector<int> pre_order;
if (!root) return pre_order;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode *temp = s.top();
pre_order.push_back(temp->val);
s.pop();
if (temp->right) s.push(temp->right);
if (temp->left) s.push(temp->left);
}
return pre_order;
}
// recursively
// LDR
vector<int> pre_order;
vector<int> preorderTraversal(TreeNode* root) {
if (root != nullptr) {
pre_order.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
return pre_order;
}
Last modified 3yr ago