前序遍历 1-(2-4-5)-3根-左-右
注意：根-左（含左边所有，左边的所有也是根左右结构）-右（右边所有）
一个栈Stack
一个动态数组ArrayList
bug:先检查root是否为空
2.递归
很简单，把根放入，递归左子树，再递归右子树
// 把root为跟的preorder加入result里面
private void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } result.add(root.val); traverse(root.left, result); traverse(root.right, result); } }
3.分治法:先分后治 有点难理解
先分，对子问题用相同的方法
bug:traverse拼写错误，ArrayList没有声明存储类型
ArrayList left = preorderTreversal(root.left);
ArrayList<Integer> left= preorderTraversal(root.right);
public class Solution { public ArrayList<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> result = new ArrayList<Integer>(); // null or leaf if (root == null) { return result; } // Divide ArrayList<Integer> left = preorderTraversal(root.left); ArrayList<Integer> right = preorderTraversal(root.right); // Conquer result.add(root.val); result.addAll(left); result.addAll(right); return result; } }
原文：http://www.cnblogs.com/yunyouhua/p/6709627.html