ac solution code


  • 0

    Explanation

    In-order: left, root, right

    The basic idea is to use stack to simulate the recursion procedure:

    1. Start from root, recursively travel to each passed node's left child until reach the tree's left leaf
    2. Then pop to left leaf's higher level node A
    3. And switch to A's right branch (Sub-process of the tree with root A.right)

    Keep the above steps until the current node is null and stack is empty.

    Runtime = O(n): As each node is visited once

    Space = O(n)

        func inorderTraversal(_ root: TreeNode?) -> [Int] {
            var res = [Int]()
            var stack = Stack<TreeNode>()
            var cur: TreeNode? = root       // Set `root` as `cur`
            
            while cur != nil || !stack.isEmpty {// <-- !stack.isEmpty
                if cur != nil {             // 1. Push cur's left branch to stack until leaf
                    stack.push(cur!)        // Push cur to stack
                    cur = cur!.left         // cur = cur.left
                } else {
                    cur = stack.pop()       // 2. Backtrack to higher level node A (stack isn't empty, via while/if condition)
                    res.append(cur!.val)    // Append cur's val
                    cur = cur!.right        // 3. Switch to the higher node A's right branch
                }
            }
            return res
        }
    

    0_1485206881610_In-order.png


Log in to reply
 

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