Solution by awice


  • 0

    Approach #1: Recursive [Accepted]

    Intuition and Algorithm

    An in-order traversal means for each node, traverse the left, then act on the node, then traverse the right. The most straightforward way is a recursive solution.

    Python

    class Solution(object):
        def inorderTraversal(self, root):
            ans = []
            def inorder(node):
                if node:
                    inorder(node.left)
                    ans.append(node.val)
                    inorder(node.right)
    
            inorder(root)
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the number of nodes in the given binary tree.

    • Space Complexity: $$O(N)$$, where $$N$$ is as defined above. Our final answer will contain all values inside the tree.


    Approach #2: Iterative [Accepted]

    Intuition

    If somehow we could emulate the call stack that is used by our compiler (or interpreter) to nest the recursive functions, we could then proceed iteratively.

    Algorithm

    The commands inorder(node.left) and inorder(node.right) get converted to the actions (VISIT, node.left) and (VISIT, node.right). The command ans.append(node.val) gets converted to the action (DO, node).

    stack emulates the behavior of the call stack: keeping a stack of actions to perform. We need to be careful to place things on the stack in the reverse order of when we want them done, as actions are popped from the end.

    To prevent mistakes and provide for clarity of code, we define enumeration constants VISIT and DO.

    Python

    class Solution(object):
        def inorderTraversal(self, root):
            VISIT, DO = 0, 1
            ans = []
            stack = [(VISIT, root)]
            while stack:
                command, node = stack.pop()
                if node:
                    if command is VISIT:
                        stack.append((VISIT, node.right))
                        stack.append((DO, node))
                        stack.append((VISIT, node.left))
                    else:
                        ans.append(node.val)
    
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the number of nodes in the given binary tree.

    • Space Complexity: $$O(N)$$, where $$N$$ is as defined above. Our final answer will contain all values inside the tree.


Log in to reply
 

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