二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

测试case

case 1

输入：root = [1,null,2,3]
输出：[1,3,2]

case 2

输入：root = []
输出：[]

case 3

输入：root = [1]
输出：[1]

解题思路

二叉树中序遍历的顺序 : 现输出左节点,在输出自身,最后输出右节点

代码实现

递归实现

// inorderTraversal 二叉树中序遍历递归实现
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 11:57 下午 2021/2/12
func inorderTraversal(root *TreeNode) []int {
  r := make([]int, 0)
  if nil == root {
    return r
  }

  mid(&r, root)
  return r
}

func mid(res *[]int, root *TreeNode) {
  //先遍历左子树
  if root.Left != nil {
    mid(res, root.Left)
  }
  //再遍历自己
  *res = append(*res, root.Val)
  //最后遍历右子树
  if root.Right != nil {
    mid(res, root.Right)
  }
}

迭代实现

// inorderTraversalWithStack 中序遍历迭代实现
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 1:13 上午 2021/2/13
func inorderTraversal(root *TreeNode) []int {
  // 中序遍历的顺序是左中右
  // 本算法采用迭代的方法完成，采用的核心工具是栈
  res := make([]int, 0)
  if root == nil {
    return res
  }
  stack := []*TreeNode{root}
  flag := false
  for len(stack) != 0 {
    if flag {
      // 当前路线左子树已经遍历完
      rightChild := stack[len(stack)-1].Right
      res = append(res, stack[len(stack)-1].Val)
      stack = stack[:len(stack)-1]
      // 说明有右子树，所以将右子树的根结点入栈
      if rightChild != nil {
        stack = append(stack, rightChild)
        // 重新初始化标志，表示该根节点的左子树还没有遍历完
        flag = false
      }
      continue
    }
    leftChild := stack[len(stack)-1].Left
    if leftChild != nil {
      // 左子树入栈
      stack = append(stack, leftChild)
      continue
    }
    // 左子树为空，说明左子树已经遍历完毕
    flag = true
  }
  return res
}