Problem

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].

思路(iterative)

1. 现将当前节点存到stack中
2. 只要stack不为空, 推出栈节点
   1. 如果它的右子节点不为空, 那么入栈
   2. 如果它的左子节点不为空, 那么入栈
3. 返回结果

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

            if (curt.right != null) {
                stack.push(curt.right);
            }
            if (curt.left != null) {
                stack.push(curt.left);
            }
        }
        return result;
    }

思路(分治)

    def preorderTraversal(self, root):
        # write your code here
        result = []
        if root is None:
            return result

        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)

        result.append(root.val)
        result.extend(left)
        result.extend(right)

        return result