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

Example

Given:

1
   / \
  2   3
 / \
4   5

return[1,2,4,5,3]

前序遍历， 根左右

1. 递归解法

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        preOrderHelper(root, ans);
        return ans;
    }

    public void preOrderHelper(TreeNode root, ArrayList<Integer> ans) {
        if (root == null) {
            return;
        }

        ans.add(root.val);
        preOrderHelper(root.left, ans);
        preOrderHelper(root.right, ans);
    }
}

1. divide and conquer

一直把树分为左右子树，然后装根进result, 再把左子树中元素放入，再把右子树中元素放入。递归下去

public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null) {
            return ans;
        }

        ArrayList<Integer> left = preorderTraversal(root.left);
        ArrayList<Integer> right = preorderTraversal(root.right);

        ans.add(root.val);
        ans.addAll(left);
        ans.addAll(right);

        return ans;
    }

1. non-recursion version (直接用stack)

因为recursion 也是用stack实现的

令狐老师云：理解，掌握，背诵。

注意要先放右子树，因为stack是first in last out

public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            ans.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }

            if (cur.left != null) {
                stack.push(cur.left);
            }

        }

        return ans;


    }