January 13, 2019

144. Binary Tree Preorder Traversal

Recursive Solution 1

This is the typical recursive method. It’s very easy to implement.

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        
        preorderTraversal(root, res);
        return res;
    }
    
    public void preorderTraversal(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorderTraversal(root.left, res);
        preorderTraversal(root.right, res);
    }
    
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.preorderTraversalHelper(root, res)
        return res
        
    def preorderTraversalHelper(self, root, res):
        if not root:
            return res
        res.append(root.val)
        self.preorderTraversalHelper(root.left, res)
        self.preorderTraversalHelper(root.right, res)

Recursive Solution 2

This is a typical divide and conquer approach to solve the problem. It might not be the optimal solution but we will use this methology a lot in solving tree’s problems.

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
                
        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);
        
        res.add(root.val);
        res.addAll(left);
        res.addAll(right);
        
        return res;
   
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

Iterative Solution

This is an iterative method - We simulate recursion in an iterative way. We need a stack to simulate recursion. Since stack is a LIFO data structure, we need to add the right subtree into stack before adding the left one.

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        
        Deque<TreeNode> stack = new LinkedList<>();
        stack.offerFirst(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pollFirst();
            res.add(cur.val);

            if (cur.right != null) {
                stack.offerFirst(cur.right);
            } 
            if (cur.left != null) {
                stack.offerFirst(cur.left);
            }
        }
        
        return res;
    }
}

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack, res = [], []
        stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val) 
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res