Binary Tree Preorder Traversal
Solution 1: recursive
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root==null) return res;
preOrder(root, res);
return res;
}
private void preOrder(TreeNode root, List<Integer> res){
if(root==null) return;
res.add(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
}
}
Solution 2: iterative
基本思路:能用递归的用非递归写用stack
public class Solution{
public List<Integer> preorderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> preorder = new ArrayList<Integer>();
if(root==null) return preorder;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
preorder.add(node.val);
if(node.right!=null) stack.push(node.right);
if(node.left!=null) stack.push(node.left);
}
return preorder;
}
}