題目連結: https://leetcode.com/problems/binary-tree-inorder-traversal/

Recursive version

    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var arr = [Int]()
        inorderHelper(root , &arr)
        return arr
    }
    
    func inorderHelper(_ root: TreeNode?, _ arr: inout [Int]) {
        guard let root = root else { return }
        inorderHelper(root.left, &arr)
        arr.append(root.val)
        inorderHelper(root.right, &arr)
    }

Iterative version

法ㄧ:

    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        if root == nil { return [] }
        var arr: [Int] = []
        var cur: TreeNode? = root
        var stack: [TreeNode?] = []
        stack.append(root)

        while !stack.isEmpty {
            while cur?.left != nil {
                stack.append(cur?.left)
                cur = cur?.left
            }
            if let node = stack.removeLast() {
                arr.append(node.val)
                cur = node.right
                stack.append(node.right)
            }
        } 
        return arr
    }

法二:

    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var arr = [Int]()
        var cur: TreeNode? = root
        var stack: [TreeNode] = [root]
        while !stack.isEmpty {
            if let left = cur?.left {
                stack.append(left)
                cur = cur?.left
            } else {
                let n = stack.removeLast()
                arr.append(n.val)
                if let right = n.right {
                    stack.append(right)
                    cur = right
                }
            }
        }
        return  arr
    }