144. Binary Tree Preorder Traversal

Information

  • Diffculty: Medium

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

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

  • Tags: Stack, Tree

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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