20210413-二叉搜索树节点最小距离.md

题目描述

原题链接：二叉搜索树节点最小距离

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

树中节点数目在范围 [2, 100] 内。

示例

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

解答

二叉搜索树，第一时间应该想到的是中序遍历后是一个升序序列。任意两不同节点之间的差值肯定不能是中序遍历里非连续访问的节点的差值，故本地的思路也很简单，中序遍历该树，每次比较得出相邻访问到节点的差值，取其中最小值就是答案啦。

就当复习下中序遍历吧，分别贴一下递归遍历和非递归遍历的模板：

//  递归中序遍历
function inOrderTraversal(root) {
  if (root.left) inOrderTraversal(root.left)
  // 在这里访问节点的值
  if (root.right) inOrderTraversal(root.right)
}

//  非递归中序遍历
function inOrderTraversal(root) {
  const stack = []
  let cur = root
  while (cur || stack.length) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      let node = stack.pop()
      //  访问该节点
      cur = node.right
    }
  }
}

本题节点数大于 2，所以 root 一定存在所以不用作 root 非空判断，套用模板即可得出答案：

//  递归版
var minDiffInBST = function (root) {
  let last = -Infinity
  let min = Infinity
  const helper = root => {
    if (root.left) helper(root.left)
    const abs = root.val - last
    if (abs < min) min = abs
    last = root.val
    if (root.right) helper(root.right)
  }
  helper(root)
  return min
}

// 非递归版
function minDiffInBST(root) {
  const stack = []
  let cur = root
  let last = -Infinity
  let min = Infinity
  while (cur || stack.length) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      let node = stack.pop()
      const abs = node.val - last
      if (abs < min) min = abs
      last = node.val
      cur = node.right
    }
  }
  return min
}

复杂度分析

• 时间复杂度：O(N)，每个节点遍历一次
• 空间复杂度：O(logN)，递归时栈空间需要 logN，非递归时代替栈的数组空间也是需要 logN