前序遍历

http://www.lintcode.com/en/problem/binary-tree-preorder-traversal

注意点：非递归；将结果作为参数传递的遍历；分治

　　　　非递归思路: 先将root放入stack，之后从stack取出来，result存值，然后将root.right放入stack，再将root.left放入stack，然后再将stack中的元素按root的方式进行操作。

 1  //分治
 2  public ArrayList<Integer> preorderTraversal(TreeNode root) {
 3      ArrayList<Integer> result = new ArrayList<Integer>();
 4      if(root == null) return result;
 5      result.add(root.val);
 6      ArrayList<Integer> left = preorderTraversal(root.left);
 7      ArrayList<Integer> right = preorderTraversal(root.right);
 8      result.addAll(left);
 9      result.addAll(right);
10      return result;
11      
12  }
13  //非递归
14   public ArrayList<Integer> preorderTraversal(TreeNode root) {
15      ArrayList<Integer> result = new ArrayList<Integer>();
16      if(root == null) return result;
17      Stack<TreeNode> s = new Stack<TreeNode>();
18      s.push(root);
19      while(!s.empty()) {
20          TreeNode node = s.pop();
21          result.add(node.val);
22          if(node.right != null) s.push(node.right);
23          if(node.left != null) s.push(node.left);
24      }
25     return result;
26       
27   }
28  //游走遍历， 要返回的结果一直作为参数在传递
29  public ArrayList<Integer> preorderTraversal(TreeNode root) {
30         ArrayList<Integer> result = new ArrayList<Integer>();
31         return    traverse(root, result);
32   }
33  private ArrayList<Integer> traverse(TreeNode root, ArrayList<Integer> result) {
34      if(root == null) return result;
35      result.add(root.val);
36      traverse(root.left, result);
37      traverse(root.right, result);
38      return result;
39  }

View Code