94. 二叉树的中序遍历 - 中等

94. 二叉树的中序遍历

二叉树遍历

二叉树中序遍历顺序为 左 根 右
当根节点的左子树为空时添加该根节点，即在 root.left = nil, 后 add root.val

递归解法

• 时间复杂度 O(n)
  其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
• 空间复杂度 O(n)
  空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var list: [Int] = []
        inorder(root, &list)
        return list
    }

    func inorder(_ root: TreeNode?, _ list: inout [Int]) {
        guard let root = root else { return }

        // 中序遍历 左 中 右
        // 即中序遍历，左根右。当根结点的左子树为空时，那么 add root.val
        // 即前序遍历，根左右。当根节点不为空时，那么 add root.val
        // 即后序遍历，左右根。当根节点的左右子树均为空时，那么 add root.val
        inorder(root.left, &list)
        list.append(root.val)
        inorder(root.right, &list)
    }

迭代解法

• 时间复杂度 O(n)
  其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
• 空间复杂度 O(n)
  空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。

func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var list: [Int] = []
        var tempList: [TreeNode] = []
        var root = root

        while root != nil || !tempList.isEmpty {
            while root != nil {
                tempList.append(root!)
                root = root?.left
            }
            root = tempList.popLast()
            list.append(root!.val)
            root = root?.right
        }
        return list
    }