cs-book

递归法：递归方法比较直接，直接按照前序遍历的定义进行递归调用， 根-左-右

func preorderTraversal(root *TreeNode) []int {
	 var result []int
	 var dfs func(node *TreeNode)
	 dfs = func(node *TreeNode) {
	 	if node == nil {
	 		return
	 	}
	 	result = append(result, node.Val)
	 	dfs(node.Left)
	 	dfs(node.Right)
	 }
	 dfs(root)
	 return result
}

迭代法：

• 初始化一个栈，将根节点压入栈中。
• 当栈不为空时，弹出栈顶节点，访问该节点。
• 将右子节点压入栈（如果存在），然后将左子节点压入栈（如果存在）。

注意：压栈的顺序是先右后左，这样出栈时才能先左后右，符合前序遍历的顺序。

func preorderTraversal1(root *TreeNode) []int {
	 if root == nil {
	 	return nil
	 }
	 var result []int
	 var stack = []*TreeNode{root}
	 for len(stack) > 0 {
	 	node := stack[len(stack)-1]
	 	// 更新stack
	 	stack = stack[:len(stack)-1]
	 	result = append(result, node.Val)
     
	 	if node.Right != nil {
	 		stack = append(stack, node.Right)
	  	}
	  	if node.Left != nil {
	  		stack = append(stack, node.Left)
	  	}
      
	  }
	  return result
}