144: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTo traverse a binary tree in a preorder fashion, we start from the root n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo traverse a binary tree in a preorder fashion, we start from the root node, visit the left subtree, then the right subtree. We will use a stack to keep track of the nodes to be visited. We first push the root node onto the stack, and then while the stack is not empty, we pop the top node and visit it. If the popped node has a right child, we push it onto the stack. If the popped node has a left child, we push it onto the stack. We continue this process until the stack is empty.\n\nIn this code, we first check if the root is None. If it is, we return an empty list. Otherwise, we create an empty stack and add the root node to it. We also create an empty list to store the result.\n\nWe then start a while loop that continues until the stack is empty. In each iteration of the loop, we pop the top node from the stack and add its value to the result list. We then check if the popped node has a right child. If it does, we push the right child onto the stack. We then check if the popped node has a left child. If it does, we push the left child onto the stack.\n\nAfter the loop ends, we return the result list. This will contain the values of the nodes in preorder traversal order.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def preorderTraversal(self, root: TreeNode) -> List[int]:\n        if not root:\n            return []\n        stack = [root]\n        result = []\n        while stack:\n            node = stack.pop()\n            result.append(node.val)\n            if node.right:\n                stack.append(node.right)\n            if node.left:\n                stack.append(node.left)\n        return result\n\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'Python3']