Skip to content

Instantly share code, notes, and snippets.

@makeapp007

makeapp007/lc144.py

Created January 13, 2022 20:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save makeapp007/f1a4830f6e46a643a5597c60a85ac318 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save makeapp007/f1a4830f6e46a643a5597c60a85ac318 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. makeapp007 created this gist Jan 13, 2022.
    44 changes: 44 additions & 0 deletions lc144.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,44 @@
    recursion
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    if not root:
    return []

    ret = []
    def dfs(node):
    if not node:
    return
    ret.append(node.val)
    dfs(node.left)
    dfs(node.right)
    dfs(root)
    return ret

    Explanation: In the dfs function, If node is not null, we store its value and visit its left side, and then its right side.

    Optimize:
    class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root: return []
    return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)


    We can also implement it iteratively.
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    if not root:
    return []

    stack, ret = [root], []
    while stack:
    node = stack.pop()
    ret.append(node.val)
    if node.right:
    stack.append(node.right)
    if node.left:
    stack.append(node.left)
    return ret

    Explanation:
    Notice that the order is Node, Left, Right. We can use a stack to store the node's right child first and then store the nodes' left child. If the node has a left child, we can get that by stack.pop()
    This runs fast than the recursive approach