Binary Tree Preorder Traversal
cheatsheet1999 opened this issue · 0 comments
cheatsheet1999 commented
Given the root of a binary tree, return the preorder traversal of its nodes' values.
A Very Straightforward Solution
var preorderTraversal = function(root, res = []) {
if (!root) return [];
res.push(root.val);
if(root.left) preorderTraversal(root.left, res);
if(root.right) preorderTraversal(root.right, res);
return res;
};
An O(N) Solution may be interesting
var preorderTraversal = function(root) {
if(!root) return [];
//We need to put a root in the stack first, because Pre-order traverse from root => left => right
let stack = [root];
let arr = [];
while(stack.length) {
let curr = stack.pop();
arr.push(curr.val);
// we want to push right subtree is because the left subtree will be visit first then.
if(curr.right) {
stack.push(curr.right);
}
if(curr.left) {
stack.push(curr.left);
}
}
return arr;
};