二叉树

首先，二叉树是一种「数据结构」。简单来说，就是一个包含节点，以及它的左右孩子的一种数据结构。

遍历方式

• 先序遍历，根节点-> 左孩子 -> 右孩子 的方式遍历，即「先序遍历」，每次遍历跟节点 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
• 中序遍历，左孩子-> 根节点->右孩子 的方式遍历，即「中序遍历」，遍历结果为 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7
• 后序遍历，左孩子->右孩子->根节点 的方式遍历，即「后序遍历」，遍历结果为 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
• 层级遍历,就是按照每一层从左向右遍历，遍历结果 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

相关题目

相关题目

这里是 4 道相关题目：

1. 144.二叉树的前序遍历
2. 94. 二叉树的中序遍历
3. 145. 二叉树的后序遍历
4. 102. 二叉树的层序遍历

这四道题目描述是相似的，就是给定一个二叉树，让我们使用一个数组来返回遍历结果，首先来看递归解法。

递归法

构造数据结构

type TreeNode struct {
 Val int
 Left *TreeNode
 Right *TreeNode
}

var res []int

root := &TreeNode{
  Val:   1,
  Left:  &TreeNode{
   Val:   2,
   Left:  &TreeNode{
    Val:   4,
    Left:  nil,
    Right: nil,
   },
   Right: &TreeNode{
    Val:   5,
    Left:  nil,
    Right: nil,
   },
  },
  Right: &TreeNode{
   Val:   3,
   Left:  &TreeNode{
    Val:   6,
    Left:  nil,
    Right: nil,
   },
   Right: &TreeNode{
    Val:   7,
    Left:  nil,
    Right: nil,
   },
  },
 }

1、前序遍历

//-- ----------------------------
//--> @Description 前序遍历
//--> @Param
//--> @return
//-- ----------------------------
func preorderTraversal(root *TreeNode){
 if root == nil{
  return
 }
 //先加入跟节点，在加入左孩子，在加入右孩子
 res = append(res,root.Val)
 preorderTraversal(root.Left)
 preorderTraversal(root.Right)
 return
}

[1 2 4 5 3 6 7]

2、中序遍历

//-- ----------------------------
//--> @Description 中序遍历
//--> @Param
//--> @return
//-- ----------------------------
func inorderTraversal(root *TreeNode){
 if root == nil {
  return
 }
 //先加入左孩子，在加入跟节点，在加入右孩子
 inorderTraversal(root.Left)
 res = append(res,root.Val)
 inorderTraversal(root.Right)
}
[4 2 5 1 6 3 7]

3、后序遍历

//-- ----------------------------
//--> @Description 后序遍历
//--> @Param
//--> @return
//-- ----------------------------
func postTraversal(root *TreeNode){
 if root == nil{
  return
 }
 postTraversal(root.Left)
 postTraversal(root.Right)
 res = append(res,root.Val)

}
[4 5 2 6 7 3 1]

迭代法

迭代法主要用到了golang的list数据结构 前序遍历

• 首先我们将右侧压入队列
• 在将左侧压入队列
• 将root写入res
• 取出尾部，不断遍历左侧，右侧
• 再次押入右侧，左侧

1、前序遍历

前序遍历：中左右 压栈顺序：右左中

//-- ----------------------------
//--> @Description 前序遍历
//--> @Param
//--> @return
//-- ----------------------------
func scanPreorderTraversal(root *TreeNode)(res []int){
 if root == nil {
  return nil
 }
 var stack = list.New()
 stack.PushBack(root.Right)
 stack.PushBack(root.Left)
 res=append(res,root.Val)
 for stack.Len()>0 {
  e:=stack.Back()
  stack.Remove(e)
  //e是Element类型，其值为e.Value.由于Value为接口，所以要断言
  node := e.Value.(*TreeNode)
  if node==nil{
   continue
  }
  res=append(res,node.Val)
  stack.PushBack(node.Right)
  stack.PushBack(node.Left)
 }
 return res

}
[1 2 4 5 3 6 7]

2、中序遍历

//-- ----------------------------
//--> @Description
//--> @Param
//--> @return
//-- ----------------------------
func scanInorderTraversal(root *TreeNode) []int {
 rootRes:=[]int{}
 if root==nil{
  return nil
 }
 stack:=list.New()
 node:=root
 //先将所有左节点找到，加入栈中
 for node!=nil{
  stack.PushBack(node)
  node=node.Left
 }
 //其次对栈中的每个节点先弹出加入到结果集中，再找到该节点的右节点的所有左节点加入栈中
 for stack.Len()>0{
  e:=stack.Back()
  node:=e.Value.(*TreeNode)
  stack.Remove(e)
  //找到该节点的右节点，再搜索他的所有左节点加入栈中
  rootRes=append(rootRes,node.Val)
  node=node.Right
  for node!=nil{
   stack.PushBack(node)
   node=node.Left
  }
 }
 return rootRes
}
[4 2 5 1 6 3 7]

3、后序遍历

迭代法后序遍历 后续遍历：左右中 压栈顺序：中右左(按照前序遍历思路)，再反转结果数组

func postorderTraversal(root *TreeNode) (res []int) {
 if root == nil {
  return nil
 }
 var stack = list.New()
 stack.PushBack(root.Left)
 stack.PushBack(root.Right)
 res=append(res,root.Val)
 for stack.Len()>0 {
  e:=stack.Back()
  stack.Remove(e)
  node := e.Value.(*TreeNode)//e是Element类型，其值为e.Value.由于Value为接口，所以要断言
  if node==nil{
   continue
  }
  res=append(res,node.Val)
  stack.PushBack(node.Left)
  stack.PushBack(node.Right)
 }
 for i:=0;i<len(res)/2;i++{
  res[i],res[len(res)-i-1] = res[len(res)-i-1],res[i]
 }
 return res
}
[4 5 2 6 7 3 1]