刷题笔记：二叉树的中序遍历（三种解法-递归，迭代，Morris）

二叉树的中序遍历：左根右
题目：https://leetcode.cn/problems/binary-tree-inorder-traversal/

首解（递归解法）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    // 边界条件
    if root == nil{
        return []int{}
    }
    // 左根右
    var res []int
    if root.Left != nil{
        res = append(res, inorderTraversal(root.Left)...)
    }
    res = append(res, root.Val)
    if root.Right != nil{
        res = append(res, inorderTraversal(root.Right)...)
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

要点1.边界条件，如果输入为空[]，需要特别处理，否则会报空指针异常。

官方解法（递归）

递归的思路是一样的，不同的是对结果数组的处理，官方引入了函数变量。将一个函数赋给变量，则变量成为“回调函数”。

func inorderTraversal(root *TreeNode) (res []int) {
    var inorder func(node *TreeNode) // 声明函数变量
    // 定义函数赋值给函数变量
    inorder = func(node *TreeNode){
        if node == nil{
            return 
        }
        inorder(node.Left) // 递归左子树
        res = append(res, node.Val) 
        // 实际上，在上面左子树的递归中就不断地将节点值加入res结果集中
        // 因此这里加入当前节点的值就ok
        inorder(node.Right) // 递归右子树
    }
    // 真正执行函数
    inorder(root)
    return // 这里res已经声明在函数签名中了，因此对res进行操作后直接返回    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

递归解法复杂度分析：时间 O(n) 每个节点都要走一遍 空间 O(n)如果树退化为链表，则需要存储所有节点

官方解法2（迭代）：

迭代的方法其实就是把递归中的栈呈现出来。golang中的stack应当是一个TreeNode数组，出栈就是删除末尾元素（stack[len-1]) 入栈就是append

func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}
    // 在遍历root不为空的情况下，或者栈不为空
    //（比如左子树遍历完了到空，那么取出栈中的根节点，再继续遍历其右子树
    for root != nil || len(stack) > 0{
        // 遍历左子树
        for root != nil{
            stack = append(stack, root)
            root = root.Left
        }
        // 此时root == nil 表示遍历完了左子树，从栈中取出根
        root = stack[len-1]
        // stack出栈末尾元素
        stack = stack[:len-1]
        // 将root的值加入（遍历到根）
        res = append(res, root.Val)
        root = root.Right
    }
    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

官方解法3（空间复杂度优化至O(1)) Morris遍历算法

用一个predecessor（前任）变量来指向当前节点的上一个节点。
设当前节点为x，首先判断x的左孩子：

1. x无左孩子，那么先将x加入结果，再将x置为x的右孩子
2. x有左孩子，则找到x子树上最后一个加入结果集的节点（最右节点），predecessor指向这个最右节点。
   然后根据predecessor是否有右孩子来判断：
3. 如果prodecessor右孩子为空，则将这个节点的右孩子（Right）指向x（因为下一个就要遍历x了），并且将x指向左节点，开始先遍历左子树（prodecessor此时保存根）
4. 如果prodecessor右孩子不为空，则我们已经遍历完其左子树，应当把x节点（根）加入结果集，然后遍历其右子树。具体操作是：我们将x的值加入结果集，并将predecessor的右孩子置为空，然后访问x的右孩子（x=x.Right)
   将x的左子树最右节点的右孩子从空变为指向x。这样遍历完左子树之后还能走回x。等于说用原本为空的一个指针保存了根节点。
   这个prodecessor节点相当于当前节点左走一步，再一直向右走到无法再走为止。

func inorderTraversal(root *TreeNode) (res []int) {
    for root != nil{
        if root.Left != nil{ // x有左孩子
            predecessor := root.Left  
            // 因为途中有可能因为prodecessor的右孩子为空所以将prodecessor指回x 这
            // 此时就不再循环
            // 1. 这里是一直往右走
            for predecessor.Right != nil && predecessor.Right != root{
                predecessor = predecessor.Right
            }
            // predecessor 是最右节点了 开始判断其右孩子
            if predecessor.Right == nil{
                predecessor.Right = root
                root = root.Left
            } else {
                // 此时predecessor.Right必定指向x节点，表示左子树已经遍历完成了
                res = append(res, root.Val) // 根加入结果集
                predecessor.Right = nil // 前驱节点的右置空 这样再次进入循环的时候prodecessor为空
                // 直接进入没有左子树的情况，见下
                root = root.Right // 开始遍历右子树
            }
        } else {
            // 没有左子树
            res = append(res, root.Val) // 根加入结果集
            root = root.Right // 开始遍历右子树
        }
    }
    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29