[数据结构与算法]144.二叉树的前序遍历

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

一、简单题，前序遍历的顺序就是根节点-左节点-右节点，递归根据遍历顺序编写程序即可。

# 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
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        def traversal(root:TreeNode):
            if not root:return root
            result.append(root.val)
            traversal(root.left)
            traversal(root.right)
        traversal(root)
        return result

时间复杂度O(n)，n为二叉树的节点数

空间复杂度O(n)，栈的开销。

二、迭代

利用迭代原理类似，只是需要将栈显示表示出来。栈先进后出，初始化将根节点入栈，为完成前序遍历的顺序根节点-左节点-右节点，右子树需要先入栈，代码如下:

# 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
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack, res = [root], []
        while stack:
            node = stack.pop()
            if node:#添加根节点的值
                res.append(node.val)
                if node.right:如果树不为空，右子树入栈
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)#左子树后入栈，则先弹出
        return res

时间复杂度O(n)，空间复杂度O(n)。

也可以先将根节点和所有左孩子入栈加入结果中再弹出到达右孩子。

# 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
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        cur, stack, res = root, [], []
        while stack or cur:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.left
            node = stack.pop()#每弹出左子树，到达右子树
            cur = node.right
        return res

时间复杂度O(n)，空间复杂度O(n)。

三、Morris 遍历

官方还有一种解答，可以在线性时间内，只占用常数空间来实现前序遍历。

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：

记作当前节点为cur。

1. 如果cur无左孩子，cur向右移动（cur=cur.right）
2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
   1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
   2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

实现以上的原则，即实现了morris遍历。

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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = list()
        if not root:
            return res
        
        p1 = root
        while p1:
            p2 = p1.left
            if p2:#左节点不为空，找到左子树上最右的节点。
                while p2.right and p2.right != p1:
                    p2 = p2.right
                if not p2.right:若右指针指向空，让其指向root，并向左移动
                    res.append(p1.val)
                    p2.right = p1
                    p1 = p1.left
                    continue
                else:#否则，让其指向空，向右移动
                    p2.right = None
            else:
                res.append(p1.val)#root没有左孩子，则向右移动。
            p1 = p1.right
        
        return res

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/er-cha-shu-de-qian-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度O(n)，空间复杂度O(1) 。