题目

给定一个二叉树，返回它的 前序 遍历。

示例:

  1. 输入: [1,null,2,3]  
  2.    1
  3.     \
  4.      2
  5.     /
  6.    3 
  8. 输出: [1,2,3]

方案一（递归）

/**
 * 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{} }
    ret := []int{}
    ret = append(ret, root.Val) // 首先遍历当前节点
    ret = append(ret, preorderTraversal(root.Left)...) // 其次遍历左子节点
    ret = append(ret, preorderTraversal(root.Right)...) // 最后遍历右子节点
    return ret
}

方案二（迭代）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    ret := []int{}
    stack := []*TreeNode{
        root,
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            ret = append(ret, node.Val)
            // 先将右子节点放入 stack, 再将左子节点放入 stack
            stack = append(stack, node.Right)
            stack = append(stack, node.Left)
        }
    }

    return ret
}

原文

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/1/