前言

最尴尬的面试不是问倒你，而是让你明明知道答案，却由于无法联想到而不知道答案！

在面试结束回去的路上，说出一句：“wo kao，原来是这样，我是会的啊！”

关于树的所有问题解法，其实就5种：前/中/后序，深/广度。

没了～，但是变化无数种！能不能准确地识别出来，这就是我写这个系列的目的了，帮助大家识别套路！

（Oh my god！！暖男有没有？关注他，关注他！）

看完本文，你能解决树五分之一的问题：中序遍历所有套路

1.简单写个中序遍历？

2.二叉搜索树的迭代器？

3.二叉搜索树的最小绝对差?

4.二叉搜索树中第k小的元素?

5.二叉搜索树中的众数?

6.二叉搜索树的范围和?

7.二叉搜索树的两数之和？

8.验证二叉搜索树？

正文

以下所有树的数据结构都是：

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

1.简单写个中序遍历？

套路解析

这是最真诚的问题了，为了表达诚意，要用最简单的方式去回答！递归实现！

（leetcode:94题）

实战算法

// 定义返回数组
var ret []int

func inOrder(node *TreeNode) []int {
  inOrderHelp(node)
  return ret
}

func inOrderHelp(node *TreeNode) {
  // 节点为nil，说明遍历尾巴了
  if node == nil {
    return
  }

  inOrderHelp(node.Left)
  // 中序遍历操作是放在中间
  ret = append(ret, node.Val)
  inOrderHelp(node.Right)
}

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

2.二叉搜索树的迭代器？

套路解析

（面试官觉得递归写的不错，想看看能不能写出非递归的方式）

所以此时走一波非递归的方式。

套路就是需要一个栈大哥来帮忙，优先获取当前节点的左节点，如果不存在则将当前节点取出，继续遍历当前节点的右节点。

（leetcode:94题）

实战算法

func inOrder(node *TreeNode) []int {
  // 边界值判断
  if node == nil {
    return []int{}
  }

  // 栈
  stack := make([]*TreeNode,0)
  // 获取根结点作为当前节点
  cur := node
  // 只要当前节点不为空，或者栈还存在东西，就继续循环
  for cur != nil || len(stack) > 0 {
    // 当前节点不为空，则取出当前节点的的左节点
    if cur != nil {
      // 将当前节点放到栈中
      stack = append(stack,cur)
      // 认为当前节点的做节点作为下一个遍历的目标
      cur = cur.Left
    } else {
      // 当前节点为空，则从栈中取出一个节点
      cur = stack[len(stack)-1]
      // 出栈
      stack = stack[:len(stack)-1]
      // 当前节点的值加到返回之中
      ret = append(ret, cur.Val)
      // 开始遍历当前节点的右节点
      cur = cur.Right
    }
  }

  return ret
}

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N) （N为节点数）

3.二叉搜索树的最小绝对差?

套路解析

二叉搜索树取相邻的值最小gap，那么此时使用中序遍历就是从小到大排序的，自然最小gap会出这个遍历之中。

套路：正常情况，中序遍历和搜索二叉树更配哦～本题计算出前一个节点和后一个节点的差值，记为min，循环判断最后得到的min值就是题目所求。

（leetcode:530题）

实战算法

// 记录前一个值的数字（因为只需要数字就好，不需要记录整个节点）
var prev int
// 返回结果
var res int

func getMinimumDifference(root *TreeNode) int {
  prev = -1
  // 将返回值只为int最大的值（这个同学们可以理解下，很好用）
  res = int(^uint(0) >> 1)
  help(root)
  return res
}

func help(root *TreeNode) {
  if root == nil {
    return
  }

  help(root.Left)

  // 这一步是关键，初始值为0
  if prev >= 0 {
    // 如果当前值减去前一个小于要返回的值，则重新设置返回值
    if root.Val - prev < res {
      res = root.Val - prev
    }
  }
  // 前文操作完之后，当前节点的值赋值给prev，当作下一个节点的前一个
  prev = root.Val

  help(root.Right)
  return
}

复杂度分析

时间复杂度：O(N)，N为树中节点个数。

空间复杂度：O(1)。

4.二叉搜索树中第k小的元素?

套路解析

二叉搜索树的中序遍历序列为递增序列，因此可中序遍历二叉搜索树，返回第K个元素即可

（leetcode: 230题）

实战算法

func getKNum(node *TreeNode, k int) int {
  if node == nil {
    return 0
  }

  stack := make([]*TreeNode,0)
  cur := node
  for cur != nil || len(stack) > 0 {
    if cur != nil {
      stack = append(stack,cur)
      cur = cur.Left
    } else {
      cur = stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      // ====start============================
      // 当k减到0的时候就是题目要的数值了
      k--
      if k == 0 {
        return cur.Val
      }
      // =====end=============================
      cur = cur.Right
    }
  }
  return 0
}

复杂度分析

时间复杂度：O(N)，N为树中节点个数。

空间复杂度：O(N)。

5.二叉搜索树中的众数?

套路解析

二叉搜索树的中序遍历序列单调不减，因此考虑中序遍历二叉搜索树。

用maxTimes记录已访问节点的最大重复元素个数，time表示当前访问节点的元素值的出现次数,用ret=[]记录结果。

若curTimes == maxTimes，则将当前节点值添加到结果集。

若curTimes > maxTimes，则以当前节点值构造新的列表作为结果，并用curTimes更新maxTimes。

中序遍历结束后，返回结果ret。

（leetcode: 501题）

实战算法

func findMode(node *TreeNode) (ret []int) {
  if node == nil {
    return 
  }
  
  maxTimes := 0
  preVal := 0
  curTimes := 0
  stack := make([]*TreeNode, 0)
  cur := node
  for cur != nil || len(stack) > 0 {
    if cur != nil {
      stack = append(stack, cur)
      cur = cur.Left
    } else {
      cur = stack[len(stack)-1]
      stack = stack[:len(stack)-1]

      // ====start============================
      // 根据curTimes是否为0来判断最初始的值
      if curTimes == 0 {
        curTimes++
        preVal = cur.Val
      } else {
        // 和前一个相等，则累计次数
        if preVal == cur.Val {
          curTimes++
        } else {
          // 否则重置次数
          preVal = cur.Val
          curTimes = 1
        }
      }

      // 判断当前累计次数与最大累计次数的关系
      if curTimes > maxTimes {
        // 更大的话，直接重置返回值
        ret = []int{cur.Val}
        maxTimes = curTimes
      } else if curTimes == maxTimes {
        // 相等的话则进行累计追加
        ret = append(ret, cur.Val)
      }
      // ====end============================

      cur = cur.Right
    }
  }
  return
}

复杂度分析

时间复杂度：O(N)，N为树中节点个数。

空间复杂度：最坏情况下为O(N)， 例如树畸形（树的高度为线性）或每个元素出现一次的情形。

6.二叉搜索树的范围和?

套路解析

当节点的值等于L时开始累加，当节点的值等于R时停止累加并返回累加的结果。

关键点：中序遍历的话，如果当前的值小于L，就没必要遍历其左节点所有的值了；同理当前值大于R就没有必要遍历其右节点所有的值了。（这个非常精髓，这样可以省下大量的遍历）

（leetcode: 938题）

实战算法

var sum int
func rangeSumBST(node *TreeNode, L int, R int) (ret int) {
  sum = 0
  BTSValue(root,L,R)
  return sum
}

func BTSValue(root *TreeNode,L,R int){
  if root == nil {
    return
  }

  // 当前的值小于L，就没必要遍历其左节点所有的值了
  if root.Val > L && root.Left != nil {
    BTSValue(root.Left,L,R)
  }
  if root.Val >= L && root.Val <= R {
    sum += root.Val
  }

  // 当前值大于R就没有必要遍历其右节点所有的值了
  if root.Right != nil && root.Val < R{
    BTSValue(root.Right,L,R)
  }
}

复杂度分析

时间复杂度：O(N), N为树中节点数。

空间复杂度：O(1)。

7.二叉搜索树的两数之和？

套路解析

中序遍历得到自增的数组，双指针来进行两数之和目标值的范围确定

（leetcode: 653题）

实战算法

var arr []int

func findTarget(node *TreeNode, k int) bool {
  arr = []int{}

  // 根据中序遍历获取到递增的数据
  med(node)

  // 双指针快速定位
  left := 0
  right := len(arr) - 1
  for left < right {
    // 如果两数相加大于k，则缩小最右边的值
    if arr[left]+arr[right] > k {
      right--
    } else if arr[left]+arr[right] < k {
      left++
    } else {
      return true
    }
  }

  return false
}

func med(node *TreeNode) {
  if node == nil {
    return
  }
  med(node.Left)
  arr = append(arr, node.Val)
  med(node.Right)
  return
}

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N)

8.验证二叉搜索树？

套路解析

如果是二叉树那说明中序遍历肯定是递增的。

实战算法

var pre *TreeNode
func isValidBST(root *TreeNode) bool {
    pre = nil
    return help(root)
}

func help(root *TreeNode) bool {
    if root == nil {
        return true
    }

    if help(root.Left) == false  {
        return false
    }

    // ====start============================
    // 前一个数存在，并且判断除了不是递增的，则直接返回false
    if pre != nil && root.Val <= pre.Val {
        return false
    }
    // 前一个节点存下来用于判断
    pre = root
    // ====end==============================

    return help(root.Right)
}

复杂度分析

时间复杂度：O(N)。

空间复杂度：O(1)。

套路总结

算法模版

func getTemp1(node *TreeNode, k int) int {
  if node == nil {
    return 0
  }

  stack := make([]*TreeNode,0)
  cur := node
  for cur != nil || len(stack) > 0 {
    if cur != nil {
      stack = append(stack,cur)
      cur = cur.Left
    } else {
      cur = stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      // ====start============================
      // 在这里根据题意做一些逻辑，其他地方基本不变了
      // 如果可以提前结束的或者需要辅助字段标记的，适当全局添加即可
      // =====end=============================
      cur = cur.Right
    }
  }
  return 0
}

// 定义返回
var ret []int
func getTemp2(node *TreeNode) []int {
  help(node)
  return ret
}

func help(node *TreeNode) {
  if node == nil {
    return
  }

  help(node.Left)
  // ====start============================
  // 在这里根据题意做一些逻辑，其他地方基本不变了
  // 如果可以提前结束的，或者忽略判断的可以在help加上if判断
  // =====end=============================
  help(node.Right)
}

时间和空间复杂度

不出意外时间复杂度都是O(N)，

空间复杂度如果用到栈了最差是O(N)，如果只是一个值那么是O(1)

后续我还会将继续揭露更多算法面试的套路～如果你有收获的话记得关注我哦～