0144. Preorder Traversal

Easy | Binary Tree + Traversal | 4 ms (99.93%), 13.3 MB (95.41%)

❓ Problem Statement

Source: LeetCode - Binary Tree Preorder Traversal GitHub: Solution / Performance

Given the root of a binary tree, return the preorder traversal of its nodes' values.

✍🏻 Constraints & Example

💡 Ideas

1. Pop the stack to retrieve the current node and append the current node's value

2. Push left-child and then right-child node onto the stack if existing

🤖 Python3

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # (base case)
        if not root: return []
        if not root.left and not root.right: return [root.val]
        
        # ==================================================
        #  Binary Tree + Pre-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        ans = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            ans.append(node.val)
            
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
                
        return ans
        
        '''
        # ==================================================
        #  Binary Tree + Pre-order Traversal               =
        # ==================================================
        # time  : O(n)
        # space : O(n)

        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
        '''

🤖 Java