144. Binary Tree Preorder Traversal

# Medium, DFS

Solution 1: Non-recursive

This is "while loop" method using stack

Use a list as stack, stack.pop() moves top element, stack.append() pushes element to top. Because Python doesn't have stack data structure
Append root to result list directly, push right leaf to stack, then push left leaf to stack
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
Until stack is empty

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

# 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

// 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

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

Self define a traversal function, pass "root" and "result", so that "result" can be changed following recursive
Add root.val to result, and traversal left, then right
When root=None, return from sub-function
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.

# 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)

// 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

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

Initialize result list
Return result list if satisfied stop condition
Divide binary tree to root, left and right
Conquer to do recursive
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

# 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

PreviousIII. Binary Tree Next94. Binary Tree Inorder Traversal

Last updated 4 years ago

hashtagSolution 1: Non-recursive

hashtagSolution 2: Recursive

hashtagSolution 3: Divide & Conquer

Solution 1: Non-recursive

Solution 2: Recursive

Solution 3: Divide & Conquer