144. 二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。

示例:

输入: [1,null,2,3]  
   1
    \
    2
    /
   3 

输出: [1,2,3]

方法一

递归

func preorderTraversal1(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        guard let root = root else { return [] }
        res.append(root.val)
        res += preorderTraversal(root.left)
        res += preorderTraversal(root.right)
        return res
    }

方法二

迭代

preorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var res: [Int] = []
        var stack: [TreeNode] = [root]
        while let node = stack.popLast() {
            res.append(node.val)
            if let right = node.right { stack.append(right) }
            if let left = node.left { stack.append(left) }
        }
        return res
    }

方法三

Morris算法

算法的步骤如下：

如果当前节点的左子节点为空时，输出当前节点，并将当前节点置为该节点的右子节点；
如果当前节点的左子节点不为空，找到当前节点左子树的最右节点（该节点为当前节点中序遍历的前驱节点）；
如果最右节点的右指针为空(right=null)，将最右节点的右指针指向当前节点，并输出当前节点（在此处输出），当前节点置为其左子节点；
如果最右节点的右指针不为空，将最右节点右指针重新置为空(恢复树的原状)，并将当前节点置为其右节点；
重复1~4，直到当前节点为空。

func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var current: TreeNode? = root
        var res: [Int] = []
        
        while current != nil {
            res.append(current!.val)
            
            if let left = current!.left {
                // Find precursor.
                var prev = left
                while let right = prev.right, right !== current {
                    prev = right
                }
                
                if let right = current!.right, prev.right === right {
                    // Restore tree.
                    current = prev.right
                    prev.right = nil
                } else {
                    // Set thread.
                    prev.right = current!.right
                    current = left
                }
            } else {
                current = current!.right
            }
        }
        return res
    }