144. Binary Tree Preorder Traversal

Posted on | In

Solution 1: accepted 2ms

Iterative method.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        if (root == null) {
            return res;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode next = stack.pop();
            res.add(next.val);
            if (next.right != null) {
                stack.push(next.right);
            } 
            if (next.left != null) {
                stack.push(next.left);
            }
        }
        
        return res;
    }
}

Solution 2: accepted 2ms

Divide and conquer recursive solution. Not good for this simple question, since the method consumes extra time, but it’s good for some more complicated questions.
Time complexity is O(n) as we visit each node only once.

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            // Divide
            List<Integer> left = preorderTraversal(root.left); // thread safe            
            List<Integer> right = preorderTraversal(root.right);
            
            // Conquer
            result.add(root.val);
            result.addAll(left); // O(n) complexity       
            result.addAll(right);            
        }
        return result;
    }
}

Solution 3: accepted 2ms

Naive recursive solution, trivial.
Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(result, root);
        return result;
    }
    
    private void traverse(List<Integer> result, TreeNode root) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        traverse(result, root.left); // thread unsafe
        traverse(result, root.right);
    }
}