[leetcode] BinaryTreePreorderTraversal

package leetcode;

import java.util.ArrayList;
import java.util.List;

import java.util.Stack;

/**
* <pre>
* 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].
* </pre>
*/
public class BinaryTreePreorderTraversal {

    public class TreeNode {
        int      val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    //Recursive
    public class Solution {

        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<Integer>();
            _preorderTraversal(root, list);
            return list;
        }

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

    //iteratively
    public class Solution2 {

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