深度优先遍历 DFS
解题思路
一想到二叉搜索树，就会想到中序遍历的结果是一个有序的序列；
根据此特性可以很容易的判断出两个最小值的差值；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
实现代码
var getMinimumDifference = function (root) {
let min = Infinity;
let pre = Infinity;
const inorderTraversal = (root) => {
// 当前结点为空时，无需进行递归
if (!root) return;
inorderTraversal(root.left); // 前序遍历左子树
min = Math.min(min, Math.abs(root.val - pre));
pre = root.val;
inorderTraversal(root.right); // 前序遍历右子树
}
inorderTraversal(root);
return min;
}
广度优先遍历 BFS
解题思路
一想到二叉搜索树，就会想到中序遍历的结果是一个有序的序列；
根据此特性可以很容易的判断出两个最小值的差值；
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，二叉树的遍历中每个节点会被访问一次且只会被访问一次； -
空间复杂度：
O(n)，空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到O(n)的级别；
实现代码
var getMinimumDifference = function (root) {
return inorderTraversal(root);
};
var inorderTraversal = (root) => {
const stk = [];
let min = Infinity;
let prev = Infinity;
while (root || stk.length > 0) {
// 1. 一直向左查找，找到最左边的节点
while (root) {
stk.push(root);
root = root.left;
}
// 2. 出栈栈顶节点
root = stk.pop();
min = Math.min(min, Math.abs(prev - root.val));
prev = root.val;
// 3. 利用栈顶节点，去寻找右孩子节点
root = root.right;
}
return min;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 617. 合并二叉树
上一篇
评论
