144. 二叉树的前序遍历 - 中等

144. 二叉树的前序遍历

二叉树遍历

二叉树的前序遍历 根 左 右

当根节点不为空时,直接把 root.val add list

递归解法

• 时间复杂度
  O(n) n 是二叉树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度
  O(n) 为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

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

    func preorder(_ root: TreeNode?, _ list: inout [Int]) {
        guard let root = root else { return }
        list.append(root.val)
        preorder(root.left, &list)
        preorder(root.right, &list)
    }

迭代解法

• 时间复杂度
  O(n) n 是二叉树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度
  O(n) 为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var list: [Int] = []
        var stackTree: [TreeNode] = []
        var root = root
        while root != nil || !stackTree.isEmpty {
            while root != nil {
                list.append(root!.val)
                stackTree.append(root!)
                root = root?.left
            }
            root = stackTree.popLast()
            root = root?.right
        }
        return list
    }