Python recursive and iterative solutions.


  • 36
    C
    # recursively
    def inorderTraversal1(self, root):
        res = []
        self.helper(root, res)
        return res
        
    def helper(self, root, res):
        if root:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)
     
    # iteratively       
    def inorderTraversal(self, root):
        res, stack = [], []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                return res
            node = stack.pop()
            res.append(node.val)
            root = node.right

  • 24
    A

    similar iterative solution

    def inorderTraversal(self, root):
        ans = []
        stack = []
        
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                tmpNode = stack.pop()
                ans.append(tmpNode.val)
                root = tmpNode.right
            
        return ans

  • 4
    Z
    For recursive solution, you can also put them in one line
       def inorderTraversal(self, root):
            return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right) if root else []

  • 0
    G

    nice code! vote up! thank you!


  • 0
    K

    my favorite solution! thanks


Log in to reply
 

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