栈方法解leetcode之145-迭代树的后序遍历

二叉树的后序遍历，递归法很简单，但是理解起来却很难，而且效率很低。如果要真正掌握后序遍历，还是用迭代法，理解起来要通透好多。推荐讲解这个视频。这里讲解的比较通透，照这个思路，一般都可以很好写出代码来。

go示例代码

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    results := make([]int, 0)
    curr := root
    stack := make([]*TreeNode,0)
    // 最后访问的元素，标记右子树是否已遍历，从而决定是否应该出栈还是不出栈
    lastVisit := curr
    for len(stack) > 0 || curr != nil {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        // 取栈顶元素，暂时不出栈
        topNode := stack[len(stack) - 1]
        // 如果元素的右子树为空，表明栈顶元素是叶子节点，没有右子树节点
        // 而如果最近访问==栈里面的右子树，则表明栈内的右子树已访问过，不需要再访问，出栈，不然会一直死徨访问右子树
        if topNode.Right == nil || topNode.Right == lastVisit {
            // 出栈，将节点值放入结果集
            results = append(results, topNode.Val)
            lastVisit = topNode
            stack = stack[:len(stack) - 1]
        } else {
            // 这里说明有右子树。那么是否出栈看是否已经遍历过
            curr = topNode.Right
        }
    }
    return results 
}

文章目录