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

题解

前序遍历模版代码。
区别在于，需要显式申明返回值，或者在函数外定义返回值变量存储节点数组。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 // 递归方式遍历
func preorderTraversal(root *TreeNode) (res []int) {
	if root == nil {
		return nil
	}
	var preorder func(r *TreeNode)
	preorder = func(r *TreeNode) {
		if r == nil {
			return
		}
		res = append(res, r.Val)
		preorder(r.Left)
		preorder(r.Right)
	}
	preorder(root)
	return
}

// 迭代方式进行前序遍历
func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	var stack []*TreeNode
	for root != nil || len(stack) > 0 {
		if root != nil {
			stack = append(stack, root)
			res = append(res, root.Val)
			root = root.Left // 因为是前序遍历，所以指向左子节点
		} else {
			// 弹出栈顶元素
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			root = root.Right
		}
	}
	return res
}