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

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

思路1：递归写法。

思路2：非递归写法，有待统一整理。

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(root==null)
            return result;
        preTravel(root, result);
        return result;
    }

    private void preTravel(TreeNode node, ArrayList<Integer> result) {
        result.add(node.val);
        if (node.left != null)
            preTravel(node.left, result);
        if (node.right != null)
            preTravel(node.right, result);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        System.out.println(new Solution().preorderTraversal(root));
    }

}

第二遍记录：

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preOrder(root,res);
        return res;
    }
    private void preOrder(TreeNode root,List<Integer> res){
        if(root!=null){
            res.add(root.val);
            preOrder(root.left,res);
            preOrder(root.right,res);
        }
        
    }
    
}

非递归写法：需要1个stack，先进右子树再进左子树，出来时候就反过来了，多画画图瞅瞅。

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root==null)
            return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode out = stack.pop();   
            res.add(out.val);
            if(out.right!=null)
                stack.push(out.right);
            if(out.left!=null)
                stack.push(out.left);

        }
        
        return res;
    }

}