Tree: 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?

前序永远是

【根】【左子树】【右子树】

中序永远是

【左子树】【根】【右子树】

后序永远是

【左子树】【右子树】【根】

1. recursion

public class Solution { ArrayList<Integer> list = new ArrayList<Integer>();//avoid each time use new list public ArrayList<Integer> preorderTraversal(TreeNode root) { if(root == null) return list; list.add(root.val); if(root.left!= null) preorderTraversal(root.left); if(root.right!=null) preorderTraversal(root.right); return list; } }

mistake: declare list out side so the whole method will use same list

2. iterative

public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode current = root; stack.push(root); while(!stack.isEmpty()){ TreeNode temp = stack.pop(); list.add(temp.val); if(temp.right!=null) stack.push(temp.right); if(temp.left != null) stack.push(temp.left); } return list; } }

learned: combined idea stack with list// use stack to store treenode not value!!