1. Description
Given a binary tree, return the preorder traversal of its nodes' values.
Note: Recursive solution is trivial, could you do it iteratively?
2. Example
Given binary tree [1,null,2,3],
return [1,2,3].
3. Code
Stack
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class LeetCode0144 {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int v) {
val = v;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
if (p != null) {
result.add(p.val);
stack.push(p);
p = p.left;
} else {
p = stack.pop();
p = p.right;
}
}
return result;
}
}
Stack
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class LeetCode0144 {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int v) {
val = v;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
while (p != null) {
result.add(p.val);
stack.push(p);
p = p.left;
}
p = stack.pop();
p = p.right;
}
return result;
}
}
Recursive
import java.util.ArrayList;
import java.util.List;
public class LeetCode0144 {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int v) {
val = v;
}
}
List<Integer> result = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return result;
}
result.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return result;
}
}
Comments | NOTHING