写点什么

LeetCode 题解:783. 二叉搜索树节点最小距离,栈,JavaScript,详细注释

作者:Lee Chen
  • 2022-11-19
    福建
  • 本文字数:711 字

    阅读完需:约 2 分钟

LeetCode题解:783. 二叉搜索树节点最小距离,栈,JavaScript,详细注释

原题链接:783. 二叉搜索树节点最小距离


解题思路:


  1. 由于二叉搜索树是有序的,任意两个节点之差的最小值,即为相邻节点的值之差的最小值。

  2. 使用中序遍历二叉搜索树,即可从左到右按顺序读取每个值,再计算与上一个节点值的之差,同时取最小值即可。


/** * @param {TreeNode} root * @return {number} */var minDiffInBST = function (root) {  let stack = [] // 使用栈辅助遍历  let current = root // 使用节点进行遍历  let min = Infinity // 记录最小值,初始值为Infinity,避免对比时出错  let prev = null // 缓存上一个节点的值
// 中序遍历二叉树 // 遍历的过程中,可能出现current为空,而stack中有元素,即为遍历到树的最底端。 // 也可能出现current有值而stack为空的情况,如遍历到二叉树的根节点。 while (current || stack.length) { // 不断向左下遍历节点,同时将所有节点入栈 // 这样就保证了总是从最左端开始遍历节点 while (current) { stack.push(current) current = current.left }
// 从栈中弹出节点,即为当前遍历的节点 // 弹出节点的顺序为从左到右。 const node = stack.pop()
// 处理中序遍历读取到的节点 // 如果prev有值,则每次比较相邻节点之差 if (prev !== null) { // 并与之前已缓存的最小值对比,min始终缓存最小值 min = Math.min(min, node.val - prev) } // 将当前节点的值缓存为prev,用于下一次比较 prev = node.val
// 不断向右侧遍历树,如果右侧节点为空,则会从栈中弹出当前子树的根节点 // 这样就形成了从左到右的遍历顺序 current = node.right }
return min}
复制代码


发布于: 刚刚阅读数: 3
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:783. 二叉搜索树节点最小距离,栈,JavaScript,详细注释_JavaScript_Lee Chen_InfoQ写作社区