144. Binary Tree Preorder Traversal

# Medium, DFS

Solution 1: Non-recursive

While loop

This is "while loop" method using stack

1. Use a list as stack, stack.pop() moves top element, stack.append() pushes element to top. Because Python doesn't have stack data structure

2. Append root to result list directly, push right leaf to stack, then push left leaf to stack

3. Poop out an element, which is a new root so append it to result list, then push its right leaf to stack, then push left leaf to stack

4. Until stack is empty

add root.val to result list instead of root, but operate root/left/right in stack list

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # consider edge case
        result = []
        stack = []
        if root == None:
            return result
        
        # regular case
        stack.append(root)
        while len(stack) > 0:
            root = stack.pop()
            result.append(root.val)
            if root.right != None:
                stack.append(root.right)
            if root.left != None:
                stack.append(root.left)
        return result

Java

// Some code
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer> ();
        Stack<TreeNode> stack = new Stack<TreeNode> ();
        
        // edge case
        if(root == null)
            return res;
            
        // regular case
        stack.push(root);
        while(stack.size() > 0) {
            root = stack.pop();
            res.add(root.val);
            if(root.right != null)
                stack.push(root.right);
            if(root.left != null)
                stack.push(root.left);
        }
        
        return res;
    }
}

Solution 2: Recursive

Recursive

Using help function to do recurcive, result list as one of two parameters, when root=None, return

Add root, traversal left, then right

return result at the end of whole functions

1. Self define a traversal function, pass "root" and "result", so that "result" can be changed following recursive

2. Add root.val to result, and traversal left, then right

3. When root=None, return from sub-function

4. return result in main function

In sub-function, only return and pass result list as a parameter; In main function, return result list???

If return result list in sub-function, it is useless because result has been passed as a parameter. In main function, if return sub-function, then the result list will be None.Because it only returns initial result lis. Why? I tried, but don't know why.

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.traversal(root, res)
        return res
    
    def traversal(self, root, res):
        # stop condition
        if root == None:
            return
        
        # regular case
        res.append(root.val)
        self.traversal(root.left, res)
        self.traversal(root.right, res)

Java

// Some code
class Solution {
    final List<Integer> res = new ArrayList<> ();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null) return res;
        
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    } 
}

Solution 3: Divide & Conquer

Divide & Conquer

Recursive the function itself, return result during recursive

Traversal left, right, and combine root, left, right at the end

return result immediately in each recursion

1. Initialize result list

2. Return result list if satisfied stop condition

3. Divide binary tree to root, left and right

4. Conquer to do recursive

5. Combine them again to get the completed result

When combine, using result.extend() instead of result.append(). Because extend means only add the elements of that list to another list, but append adds whole list directly

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:def preorderTraversal(self, root: TreeNode) -> List[int]:
        # consider edge case
        result = []
        if root == None:
            return result
        
        # regular case
        # divide
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        
        # conquer
        result.append(root.val)
        result.extend(left)
        result.extend(right)
        return result