Leetcode 二叉树的前序遍历

0 题目描述

Leetcode原题链接：二叉树的前序遍历

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right

1 递归解法

深度优先搜索（DFS）

在这个策略中，我们采用深度作为优先级，以便从根开始一直到达某个确定的叶子，然后再返回根到达另一个分支。 深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为前序遍历，中序遍历和后序遍历。

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

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

2 迭代解法（堆栈）

宽度优先搜索（BFS）

我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: White, Gray = 0, 1 res = [] stack = [(White,root)] while stack: color, node = stack.pop() if not node: continue if color == White: stack.append((White,node.right)) stack.append((White,node.left)) stack.append((Gray,node)) else: res.append(node.val) return res

算法复杂度 时间复杂度：访问每个节点恰好一次，时间复杂度为$O(N)$，其中$N$是节点的个数，也就是树的大小。 空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是$O(N)$。

3 Morris 前序遍历

方法基于莫里斯的文章，可以优化空间复杂度。算法不会使用额外空间，只需要保存最终的输出结果。如果实时输出结果，那么空间复杂度是 $O(1)$。

class Solution(object): def preorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ node, res = root, [] while node: if not node.left: res.append(node.val) node = node.right else: pre = node.left while pre.right and pre.right is not node: pre = pre.right if not pre.right: res.append(node.val) pre.right = node node = node.left else: pre.right = None node = node.right return res

算法复杂度 时间复杂度：$O(n)$，其中 $n$ 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)$=$O(n)$。 空间复杂度：$O(1)$。

参考资料

二叉树的中序遍历 – Python实现三种解法 Leetcode 二叉树的前序遍历