LeetCode 144. Binary Tree Preorder Traversal

Question

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

Explanation

依旧是两种方法，递归和遍历。递归非常容易，分治即可。遍历需要用到Stack这个数据结构，想清楚顺序就好。

Code

public class Solution {
     public List<Integer> preorderTraversal(TreeNode root) {
         List<Integer> result = new ArrayList<>();
         if (root == null) return result;
         List<Integer> left = preorderTraversal(root.left);
         List<Integer> right = preorderTraversal(root.right);

         result.add(root.val);
         result.addAll(left);
         result.addAll(right);
         return result;
     }
    // Iterative solution
    // public List<Integer> preorderTraversal(TreeNode root) {
    //     Stack<TreeNode> stack = new Stack<>();
    //     List<Integer> result = new ArrayList<>();
    //     if (root == null) return result;
    //     TreeNode tmp = root;
    //     stack.add(root);
    //     while (!stack.isEmpty()) {
    //         tmp = stack.pop();
    //         result.add(tmp.val);
    //         if (tmp.right != null) stack.push(tmp.right);
    //         if (tmp.left != null) stack.push(tmp.left);
    //     }
    //     return result;
    //     }
}