迭代 + 栈
解题思路
非递归的遍历时，算法需要借助一个栈 stk 来存储根节点，利用根节点找到相应的右节点；
首先访问根节点，如果此节点的左子树不为空，将此根节点入栈 res 中，一直查找左节点直到节点的左子树为空时；
从堆栈 stk 中弹出一个根节点，利用根节点找到右节点，再按照相同的方法访问节点；
如此反复，直到堆栈为空时结束；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
实现代码
var minDiffInBST = (root) => {
let min = Infinity;
let prev = Infinity;
const stk = [];
let curr = root;
while (curr !== null || stk.length > 0) {
if (curr !== null) {
// 将所有的左节点依次入栈
stk.push(curr);
curr = curr.left;
} else {
// 左子树处理完毕，将 stk 出栈处理根节点，根据根节点找到右节点
curr = stk.pop();
min = Math.min(min, Math.abs(prev - curr.val));
prev = curr.val;
curr = curr.right; // 处理右子树
}
}
return min;
};
递归
解题思路
由于是 BST 则 中序遍历 是一个升序序列；
只需要判断 前后两个相邻的节点值是否是最小即可；
递归的方式判断；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉搜索树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到O(n)级别；
实现代码
var minDiffInBST = function (root) {
const dfs = (root) => {
if (root === null) return;
dfs(root.left);
min = Math.min(min, Math.abs(prev - root.val));
prev = root.val;
dfs(root.right);
};
let min = Infinity;
let prev = Infinity;
dfs(root);
return min;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 92. 反转链表 II
上一篇
评论
