Standard DFS Python Inorder code


  • 0
    W
    class Solution:
        # @param root, a tree node
        # @return a list of integers
        def inorderTraversal(self, root):
            if root==None:
                return []
            s,re,node=[],[],root
            while s or node:
                if node:
                    s.append(node)
                    if node.left:
                        node=node.left
                    else:
                        node=None
                else:
                    node=s.pop(-1)
                    re.append(node.val)
                    if node.right:
                        node=node.right
                    else:
                        node=None
            return re

  • 0
    N

    I liked your solution but you can make it a bit shorter and still have it doing the exact same thing:

    1. If root is None you won't enter the while loop so the first check is not necessary.
    2. Your if node.left ... else statement is equal to node = node.left
    3. Your if node.right ... else statement is equal to node = node.right
    class Solution(object):
        def inorderTraversal(self, root):
            res, stack = [], []
            while stack or root:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    root = stack.pop()
                    res.append(root.val)
                    root = root.right
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.