代码随想录算法训练营第12天 | 树的遍历

（本合集全部为Go语言实现）

相关文章链接：递归遍历 迭代遍历 统一迭代法
相关视频链接：

Leetcode94

状态：
实现过程中的难点：迭代法的模拟过程比较难想

个人写法

递归方式

func inorderTraversal(root *TreeNode) []int {
  var res []int
  inorderTraversal0(root, &res)
  return res
}

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

  inorderTraversal0(root.Left, res)
  *res = append(*res, root.Val)
  inorderTraversal0(root.Right, res)
}

迭代写法

通过模拟遍历过程，整体可以分成两种情况：

• 指针指向的节点不为空，此时需要先将节点入栈，而不是先进行处理，因为中序遍历顺序为左中右

• 指针指向的节点为空，此时又有两种情况：

  • 指针节点为左孩子时，指针指向栈顶元素，为父节点，表示父节点的左子树遍历完成
  • 指针节点为右孩子时，指针指向栈顶元素，为父节点的某个父节点（因为父节点可能是右子树），表示这个父节点的左子树遍历完成

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

  var stack []*TreeNode
  push := func(node *TreeNode) {
    stack = append(stack, node)
  }
  pop := func() *TreeNode {
    tmp := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    return tmp
  }

  curNode := root
  for curNode != nil || len(stack) != 0 {
    if curNode != nil {
      push(curNode)
      curNode = curNode.Left
    } else {
      curNode = pop()
      res = append(res, curNode.Val)
      curNode = curNode.Right
    }
  }
  return res
}

Leetcode145

状态：
实现过程中的难点：

个人写法

递归写法

func postorderTraversal(root *TreeNode) []int {
  var res []int
  postorderTraversal0(root, &res)
  return res
}

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

  postorderTraversal0(root.Left, res)
  postorderTraversal0(root.Right, res)
  *res = append(*res, root.Val)
}

迭代写法

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

  var stack []*TreeNode
  push := func(node *TreeNode) {
    stack = append(stack, node)
  }
  pop := func() *TreeNode {
    tmp := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    return tmp
  }

  push(root)
  for len(stack) > 0 {
    curNode := pop()

    res = append(res, curNode.Val)
    if curNode.Left != nil {
      push(curNode.Left)
    }
    if curNode.Right != nil {
      push(curNode.Right)
    }
  }
  for i, j := 0, len(res) - 1; i < j; i, j = i + 1, j - 1 {
    res[i], res[j] = res[j], res[i]
  }
  return res
}

Leetcode144

状态：
实现过程中的难点：

个人写法

递归写法

func preorderTraversal(root *TreeNode) []int {
  var res []int
  preorderTraversal0(root, &res)
  return res
}

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

  *res = append(*res, root.Val)
  preorderTraversal0(root.Left, res)
  preorderTraversal0(root.Right, res)
}

迭代写法

func preorderTraversal(root *TreeNode) []int {
  var res []int

  if root == nil {
    return res
  }

  var stack []*TreeNode
  push := func(node *TreeNode) {
    stack = append(stack, node)
  }
  pop := func() *TreeNode {
    tmp := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    return tmp
  }

  push(root)
  for len(stack) > 0 {
    curNode := pop()

    res = append(res, curNode.Val)
    if curNode.Right != nil {
      push(curNode.Right)
    }
    if curNode.Left != nil {
      push(curNode.Left)
    }
  }
  
  return res
}

今日收获

• 主要是又复习了一下迭代法，尤其是的中序遍历的迭代法

学习时长：2小时左右