144. Binary Tree Prorder Traversal

Intuition

This could be solved simply by recursion. But in this solution, I would try to use stack directly instead of recursion.

The preorder traversal is that, for each node, we first visit itself, then visit the left and right subtree of this node. So the solution is really straight forward.

Solution

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        order = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node is None:
                continue
            order.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
        return order

Information

  • Created: 2018-04-29 15:32:15

  • Last Motified: 2020-01-12 17:41:05

  • Tags: Stack, Tree