题目

给你二叉树的根节点 root，返回它节点值的 前序遍历。

示例 1：

• 输入：root = [1,null,2,3]
• 输出：[1,2,3]

示例 2：

• 输入：root = []
• 输出：[]

示例 3：

• 输入：root = [1]
• 输出：[1]

示例 4：

• 输入：root = [1,2]
• 输出：[1,2]

示例 5：

• 输入：root = [1,null,2]
• 输出：[1,2]

方法一：递归

思路及解法

首先我们需要了解什么是二叉树的前序遍历：按照访问根节点 -- 左子树 -- 右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

代码

class Solution {
    func preorder(_ root: TreeNode?, _ res: inout [Int]) {
        guard nil != root else {
            return
        }
        res.append(root!.val)
        preorder(root?.left, &res)
        preorder(root?.right, &res)
    }
    
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        preorder(root, &res)
        return res
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

方法二：迭代

思路及解法

我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

代码

class Solution {
   func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
       if nil == root {
           return res
       }
       
       var stack: [TreeNode?] = []
       var node: TreeNode? = root
       
       while !stack.isEmpty || nil != node {
           while nil != node {
               res.append(node!.val)
               stack.append(node)
               node = node?.left
           }
           node = stack.removeLast()?.right
       }
       return res
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

• 空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。

方法三：Morris 遍历

思路及解法

有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

1. 新建临时节点，令该节点为 root；
2. 如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
3. 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
   • 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
   • 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
4. 重复步骤 2 和步骤 3，直到遍历结束。

这样我们利用 Morris 遍历的方法，前序遍历该二叉树，即可实现线性时间与常数空间的遍历。

代码

class Solution {
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        if nil == root {
            return res
        }
        
        var p1: TreeNode? = root
        var p2: TreeNode? = nil
        while (nil != p1) {
            p2 = p1?.left
            if (nil != p2) {
                while (nil != p2?.right && p2?.right != p1) {
                    p2 = p2?.right
                }
                if (nil == p2?.right) {
                    res.append(p1!.val)
                    p2?.right = p1
                    p1 = p1?.left
                    continue;
                } else {
                    p2?.right = nil
                }
            } else {
                res.append(p1!.val)
            }
            p1 = p1?.right
        }
        return res
    }
}

extension TreeNode: Equatable {
    public static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {
        return lhs === rhs
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次。

• 空间复杂度：O(1)。只操作已经存在的指针（树的空闲指针），因此只需要常数的额外空间。