二叉树的前序遍历

二叉树的前序遍历： 根->左->右

递归

访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树

python

# 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]:
        res = []
        def handle(root):
            if not root:
                return
            res.append(root.val)
            handle(root.left)
            handle(root.right)
        handle(root)
        return res

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    var handle func(*TreeNode)
    handle = func(root *TreeNode) {
         if root== nil {
            return
        }
        res = append(res, root.Val)
        handle(root.Left)
        handle(root.Right)
        return
    }
    handle(root)
    return res
}

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

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

迭代

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

手动构造栈，for循环条件，节点不为nil，栈的长度大于0，嵌套for循环
里层for循环，节点不为nil，把该节点的值放入结果，该节点都放入栈，然后节点等于节点的下层左边节点，进行迭代，下层节点的左边有值继续迭代，直到左边节点为nil，里层for循环结束

外层for循环，取节点为栈里最后一个节点，就是里层for循环里，左边节点为nil的上层节点的右边节点 减少栈，然后再次外层foe循环，遍历这个右边节点的左边，左边为nil，则节点等于上一层放入的节点的右边节点，右边节点为nil，则取栈里上一个节点

也就是
内层for循环，顶层到底层逐层遍历左边节点，把节点的值压入结果
外层for循环，底层往回到顶层遍历右边节点，把节点压入结果

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    node := root
    vals := []int{}
    for node != nil || len(stack) > 0 {
        for node != nil {
            vals = append(vals, node.Val)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    return vals
}

python

# 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 = []
        node = root
        res = []
        while node or stack:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left
            node = stack[-1].right
            stack = stack[:len(stack)-1]
        return res
        

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

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

Morris 遍历

记录当前处理节点cur
tail记录当前节点下层左子树的下层最右节点
外层循环节点不为空
如果tail不为空，while循环，找到所有tail的位置，直到tail为空，也就是找到左子树的最后一个右节点
也就是第一层，往下第一层的左节点，第二层的右节点（到第三层），直到找到最后的右节点

如果tail.right为空了,则输出这个节点，并设tail.right为当前节点cur

然后cur= cur.left设为左节点，继续外层循环，也就是第二层为根，找到第二层的左节点，
第三层，往下第三层的右节点往下，直到为空

然后指向cur为第二层为根节点，指向第三层的左节点，找tail.right,为空则记录结果

直到tail为none，也就是cur的左子节点为空了，说明左子树处理完了，记录结果

cur=cur.right

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

新建临时节点，令该节点为 root；

如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；

如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：

如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。

如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。

重复步骤 2 和步骤 3，直到遍历结束

Morris遍历的通解：
1）cur无左子节点，向右移动
2）cur有左子节点，则找到cur左子节点的最右子节点，即为前驱节点pre
2-1) pre.right == null，说明是首次访问，将pre.right指向cur，cur向左移
2-2) pre.right == cur，说明是第二次访问，将pre.right置空，cur向右移动
3) cur为空时遍历结束

python

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 结果列表
        res = list()
        # 如果不是根节点，返回
        if not root:
            return res
        # 设定起始遍历节点，p1
        p1 = root
        # 遍历树，节点有值就一直遍历
        while p1:
            # 选取该节点的左子树节点，该节点的第二层，并设为p2，p2位第二层
            p2 = p1.left
            # 如果该节点有左子树节点
            if p2:
                # 对第二层的p2节点的右子树遍历，p2.right为第三层
                # 有值，且不为p1，没有指向第一层，直到 p2.right为空
                # 一直向下遍历，设p2为其下一层的右子树节点
                while p2.right and p2.right != p1:
                    p2 = p2.right
                # 遍历到最底层，p2.right为空了
                if not p2.right:
                    # 第一层的节点，放入结果
                    res.append(p1.val)
                    # 修改 p2.right，指向第一层的节点
                    p2.right = p1
                    # p1到第二层的左子树节点
                    p1 = p1.left
                    # 返回while继续遍历，第二次循环，就把第二层的左子树节点放入结果
                    continue
                else:
                    p2.right = None
            else:
                res.append(p1.val)
            p1 = p1.right
        
        return res

GO

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }
    p1 := root
    for {
        if p1 == nil {
            break
        }
        p2 := p1.Left
        if p2 != nil {
            for {
                if p2.Right != nil && p2.Right != p1 {
                    p2 = p2.Right
                } else {
                    break
                }
            }
            if p2.Right == nil {
                res = append(res, p1.Val)
                p2.Right = p1
                p1 = p1.Left
                continue
            } else {
                p2.Right = nil
            }
        } else{
            res = append(res, p1.Val)
        }
        p1 = p1.Right
    }
    return res
}

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

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