66. Binary Tree Preorder Travers

题目：

Given a binary tree, return the preorder traversal of its nodes' values.

给定一个二叉树，返回该二叉树节点数值的先续遍历。

一般树问题有两种解题思路，递归和非递归解法。

代码明了，思路简洁是递归方法的优势所在。在使用递归的时候也有两种思路可选，普通遍历，分治。

1. 遍历：每次调用helper方法时都需要传入一个名为 result 的 List，这部分的值保存入栈中，直到该方法遍历到底部再依次返回后弹出，造成栈溢出

public List<Integer> preorderTraversal(TreeNode root) {

    List<Integer> result = new ArrayList<>(); 

    helper(result, root); 

    return result; 

} 

public void helper( List<Integer> result, TreeNode root ) {

    if( root == null)

        return;

    result.add(root.val);

    helper( result, root.left);

    helper( result, root.right);

    return;

}

2. 分治: 使用了全局变量，避免了遍历方法中出现的空间浪费情况，以返回值的方式逐步自上到下更新result的结果。

<Integer> result = new ArrayList<>(); 

public List<Integer> preorderTraversal(TreeNode root) {

    if(root == null)

        return null;

    result.add(root.val);

    preorderTraversal( root.left );

    preorderTraversal( root.right );

    return result;

}

3. 非递归: 非递归方法相对节省运行空间，运行效率高。

使用中借助了 Stack 的特性：先进后出。 由于是先续遍历，我们要得到的顺序为 root->left->right, 所以在把子节点压入栈中的时候需要注意一点，如果我们先压入左节点，再压入右节点，那么出栈时的顺序就是先右后左，显然是不对的。所以在把当前节点存入 list 后，要先把右节点压入栈，再压入左节点。

public List<Integer> preorderTraversal(TreeNode root) {

    if( root == null) 

        return null; 

    List<Integer> result = new ArrayList<>(); 

    Stack<TreeNode> stack = new Stack<>();

    stack.push(root);

    while(!stack.isEmpty()){

        TreeNode tmp = stack.pop();

        result.add(tmp.val);

        if(tmp.right != null)

            stack.push(tmp.right);

        if(tmp.left != null)

            stack.push(tmp.left);

    }

    return result;

}