二叉树的遍历

 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
30

func preorderWithMorris(root *TreeNode) {
    cur := root
    for cur != nil {
        mostRight := cur.Left
        if mostRight != nil {
            // 进入到这里说明当前节点有左子树，有如下两种可能：
            // 1. 第一次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向空
            // 2. 第二次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向 cur
            for mostRight.Right != nil && mostRight.Right != cur {
                mostRight = mostRight.Right
            }
            if mostRight.Right == cur {
                // 如果 mostRight.Right == cur，则说明这是第二次访问 cur 节点，
                // 左子树已经遍历完成
                mostRight.Right = nil
                cur = cur.Right
            } else {
                fmt.Println(cur.Val)// 前序遍历代码位置，这里只是简单地打印节点值
                // 如果 mostRight.Right == nil，则说明这是第一次访问 cur 节点，
                // 左子树还未遍历，移动 cur 指针到左子树，准备遍历左子树
                mostRight.Right = cur
                cur = cur.Left
            }
        } else {
            fmt.Println(cur.Val)// 前序遍历代码位置，这里只是简单地打印节点值
            // 没有左子树，直接转到 Right 指针指向的节点
            cur = cur.Right
        }
    }
}

 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
30

func inorderWithMorris(root *TreeNode) {
    cur := root
    for cur != nil {
        mostRight := cur.Left
        if mostRight != nil {
            // 进入到这里说明当前节点有左子树，有如下两种可能：
            // 1. 第一次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向空
            // 2. 第二次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向 cur
            for mostRight.Right != nil && mostRight.Right != cur {
                mostRight = mostRight.Right
            }
            if mostRight.Right == cur {
                fmt.Println(cur.Val) // 中序遍历代码位置，这里只是简单地打印节点值
                // 如果 mostRight.Right == cur，则说明这是第二次访问 cur 节点，
                // 左子树已经遍历完成
                mostRight.Right = nil
                cur = cur.Right
            } else {
                // 如果 mostRight.Right == nil，则说明这是第一次访问 cur 节点，
                // 左子树还未遍历，移动 cur 指针到左子树，准备遍历左子树
                mostRight.Right = cur
                cur = cur.Left
            }
        } else {
            fmt.Println(cur.Val) // 中序遍历代码位置，这里只是简单地打印节点值
            // 没有左子树，直接转到 Right 指针指向的节点
            cur = cur.Right
        }
    }
}

 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

func postorderWithMorris(root *TreeNode) {
    var reverseList func(head *TreeNode) *TreeNode
    reverseList = func(head *TreeNode) *TreeNode {
        var prev *TreeNode
        cur := head
        for cur != nil {
            next := cur.Right
            cur.Right = prev
            prev = cur
            cur = next
        }
        return prev
    }

    var printNodeVal func(root *TreeNode)
    printNodeVal = func(root *TreeNode) {
        newHead := reverseList(root)
        cur := newHead
        for cur != nil {
            fmt.Println(cur.Val) // 后序遍历中对节点执行的操作，这里只是简单地打印节点值
            cur = cur.Right
        }
        reverseList(newHead)
    }
    cur := root
    for cur != nil {
        mostRight := cur.Left
        if mostRight != nil {
            // 进入到这里说明当前节点有左子树，有如下两种可能：
            // 1. 第一次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向空
            // 2. 第二次访问当前节点，此时当前节点左子树的最右节点的 Right 指针指向 cur
            for mostRight.Right != nil && mostRight.Right != cur {
                mostRight = mostRight.Right
            }
            if mostRight.Right == cur {
                // 如果 mostRight.Right == cur，则说明这是第二次访问 cur 节点，
                // 左子树已经遍历完成
                mostRight.Right = nil
                printNodeVal(cur.Left)
                cur = cur.Right
            } else {
                // 如果 mostRight.Right == nil，则说明这是第一次访问 cur 节点，
                // 左子树还未遍历，移动 cur 指针到左子树，准备遍历左子树
                mostRight.Right = cur
                cur = cur.Left
            }
        } else {
            // 没有左子树，直接转到 Right 指针指向的节点
            cur = cur.Right
        }
    }
    printNodeVal(root) // 在这里还要执行一次 printNodeVal
}