144. 二叉树的前序遍历

题目#

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路#

递归解法非常简单。

迭代解法同样，是手动维护访问栈。由于前序遍历是先访问根节点，再遍历左、右子树，因此非常简单。

代码#

递归#

func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    preorder(root, &res)
    return res
}

func preorder(root *TreeNode, res *[]int) {
    if root != nil {
        *res = append(*res, root.Val)
        preorder(root.Left, res)
        preorder(root.Right, res)
    }
}

迭代#

func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res
    }

    // 访问栈
    stack := []*TreeNode{}
    stack = append(stack, root)

    for len(stack) != 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 先访问节点
        if node != nil {
            res = append(res, node.Val)
        }
        // 之后是左右子树
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }

    return res
}