[Leetcode] 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?

使用递归比较容易写，使用Morris遍历可以达到O(1)的空间复杂度，先序遍历和中序遍历的写法比较类似，唯一不同的地方就在于将节点的val输出的时间不一样。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        preorder(root, list);
        return list;
    }
    public void preorder(TreeNode root, List<Integer> list) {
        if(root == null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode cur = root, temp;
        while(cur != null) {
            if(cur.left == null) {
                list.add(cur.val);
                cur = cur.right;
            }
            else {
                temp = cur.left;
                while(temp.right != null && temp.right != cur) temp = temp.right;
                if(temp.right == null) {
                    list.add(cur.val);
                    temp.right = cur;
                    cur = cur.left;
                }
                else {
                    temp.right = null;
                    cur = cur.right;
                }
            }
        }
        
        return list;
    }