Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes‘ values.
Example
Given binary tree {1,#,2,3}:
1
2
/
3
return [1,2,3].
SOLUTION 1:
这题首先应该想到递归做法，最简单直观的也是递归做法。首先先来说一下递归是什么，递归其实就是自己调用自己，但是注意的是，递归往往没有返回值。
在用递归方法的时候要定义清楚，递归方法接收了什么参数，做了什么事情，在这个题里面，看到返回值是个ArrayList，那么首先应该new一个存放结果的ArrayList并且用于最后返回，
所以说递归函数一定会接受一个ArrayList，而且一定会有一个根结点，所以这个递归函数应该是这样的：traversal(TreeNode root, ArrayList<Integer> result){}，然后定义这个函数做了什么事情，就是把以root为根的前序遍历加到result里面。
时间复杂度就是O(h) [h是二叉树高度，换算一下就是，设n为点个数，h ＝ log n]
也就是O(log n)
后面就很简单的看一下代码了：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null){
return result;
}
traversal(root, result);
return result;
}
private void traversal(TreeNode root, ArrayList<Integer> result){
if (root == null){
return;
}
result.add(root.val);
traversal(root.left, result);
traversal(root.right, result);
}
}
SOLUTION 2:
第二种方法，就是几乎使用所有二叉树的分治法，分治法其实也是一种递归方法，不过相当于把给的参数分成两部分，分别处理，在二叉树这种结构中，天然的把自己分成了两个部分，可以直接使用分治法。
注意的是分治法一般都是有返回值的，这个跟一般的递归方法是不一样的。
再注意的是，在极端情况下（二叉树退化成链表）这时时间复杂度会从O(log n)退化成O(n) [n 是点个数]
代码如下：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null){
return result;
}
// 左右两边分别递归处理＝＝＝》分治法之“分”
ArrayList<Integer> left = preorderTraversal(root.left);
ArrayList<Integer> right = preorderTraversal(root.right);
// 左右两边再跟根结点合并
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}
}
SOLUTION 3:
比较重要的是第三种方法，这种方法是非递归方法。
对于递归方法，它的一个坏处就是会stack overflow，就是栈溢出，这个是由于当运行一个程序的时候，系统会自动分配给这个程序一块栈内存，8MB，也就是说，递归过深的时候，就会消耗大量栈空间，当其超过8MB时候就会栈溢出，所以，往往能用非递归就不用递归，除非非递归太复杂了。
非递归的解体方法就是用栈（stack）模拟递归。具体方法见代码：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Preorder in ArrayList which contains node values.
*/
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty()){
TreeNode temp = stack.pop();
result.add(temp.val);
// 由于stack是先进后出，所以压栈时候要先压入right子树
// 这样才能保证出栈时候是左先出，右后出
if (temp.right != null){
stack.push(temp.right);
}
if (temp.left != null){
stack.push(temp.left);
}
}
return result;
}
}
[lintcode] Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/tritritri/p/4856833.html