栈方法解leetcode之144-迭代树的前序遍历

前序相比后序遍历，理解起来还是较容易，下面的代码如果不明白。可以画一个简单的二叉树，照代码观察下栈内的数据变化，很容易明白。

golang示例代码

 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


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    // 前序为根左右
    if root == nil {
        return []int{}
    }
    results := make([]int, 0)
    stack := make([]*TreeNode, 0)
    // 先将根节点加入栈内，不然下面的循环执行不下去
    stack = append(stack, root)
    for len(stack) > 0 {
        // 从栈中取出节点，并出栈
        topNode := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        // 将出栈的值加入到结果集中
        results = append(results, topNode.Val)
        // 栈为先进后出，所以右子树要先入栈
        // 如果栈顶元素的右子树不为空，加入栈内，继续循环
        if topNode.Right != nil {
            stack = append(stack, topNode.Right)
        }
        // 如果栈顶元素的左子树不为空，加入栈内，继续循环
        if topNode.Left != nil {
            stack = append(stack, topNode.Left)
        }
    }
    // 当栈空时，树就遍历完成了
    return results
}

文章目录