leetcode 530 - Minimum Absolute Difference in BST
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值, 提示：树中至少有 2 个节点。
最直观的想法，就是把BST通过inorder dfs recursion转换成有序数组，然后遍历一遍数组，就统计出来最小差值了(solution1), 第二个解法也是基于inorder dfs recursion， 但是不用开辟数组，可以直接在递归里maintain结果变量（solution2）. 这道题也是lc98的变形题
//👍 Solution 1: bst dfs inorder to create visited array, then find the Minimum Diff of that array
var getMinimumDifference = function (root) {
const visited = [];
const helper = (node) => {
if (!node) return;
if (node.left) helper(node.left);
visited.push(node.val);
if (node.right) helper(node.right);
};
helper(root);
let minAbsDiff = Infinity;
for (let i = 0; i < visited.length; i++) {
const diff = Math.abs(visited[i] - visited[i + 1]);
if (diff < minAbsDiff) {
minAbsDiff = diff;
}
}
return minAbsDiff;
};
//👍👍 Solution 2: bst dfs inorder, but no need to create array!
var getMinimumDifference = function (root) {
let pre = null;
let minDiff = Infinity;
const helper = (node) => {
if (!node) return;
if (node.left) helper(node.left);
if (pre) {
const currDiff = Math.abs(pre.val - node.val);
minDiff = Math.min(minDiff, currDiff);
}
pre = node;
if (node.right) helper(node.right);
};
helper(root);
return minDiff;
};
leetcode 501 - Find Mode in Binary Search Tree
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素.
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
example:
最直观的方法是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合(solution1), 第二个解法利用了bst特性，既然是搜索树，它中序遍历就是有序的，遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
//👍 Solution 1: dfs inorder to create visited map, then find the most high frequency of that map
var findMode = function (root) {
const map = new Map();
const helper = (node) => {
if (!node) return;
if (node.left) helper(node.left);
map.set(node.val, map.get(node.val) + 1 || 1);
if (node.right) helper(node.right);
};
helper(root);
let maxCount = map.get(root.val);
let result = [];
for (let [key, value] of map) {
if (value === maxCount) {
result.push(key);
}
if (value > maxCount) {
result = [];
maxCount = value;
result.push(key);
}
}
return result;
};
//👍👍 Solution 2: dfs inorder, but no need to create map!
var findMode = function (root) {
let result = [];
let pre = null;
let count = 0; // 记录单个元素出现的频率
let maxCount = 1; // 记录整个树中某元素出现的最大频率
const helper = (node) => {
if (!node) return;
helper(node.left);
if (!pre) count = 1; // 第一个节点
else if (pre && node.val === pre.val) count++; // 与前一个节点数值相同
else count = 1; // 与前一个节点数值不同
pre = node; // 更新上一个节点
if (count === maxCount) {
// 如果和最大值相同，放进result中
result.push(node.val);
} else if (count > maxCount) {
// 如果计数大于最大值频率，要更新最大频率，要清空result，因为之前result里的元素都失效了， 最后更新result
maxCount = count;
result = [];
result.push(node.val);
}
helper(node.right);
};
helper(root);
return result;
};
leetcode 236 - Lowest Common Ancestor of a Binary Tree
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。那么二叉树如何可以自底向上查找呢？回溯啊，二叉树回溯的过程就是从底到上。后序post_order遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑， 最后通过回溯将结果返回给头结点
这道题目刷过的同学未必真正了解这里面回溯的过程，以及结果是如何一层一层传上去的。
那么我给大家归纳如下三点：
- 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
- 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
- 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
- 可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。 本题没有给出迭代法，因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。
/* 👍👍 使用recursuib的方法, 需要从下到上，所以使用post order: */
var lowestCommonAncestor = function (root, p, q) {
const travelTree = function (node, p, q) {
// 确定递归终止条件
if (!node) return null;
if (node === p || node === q) return node; // find the p or q node, then return this p or q
let left = travelTree(node.left, p, q);
let right = travelTree(node.right, p, q);
if (left && right) return root; //如果left和right都不为空，说明此时root就是最近公共节点。
if (!left) return right; //如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然
return left;
};
return travelTree(root, p, q);
};
学习总结：
- BST常用in-order dfs
- 寻找公共祖先要用post-order dfs
Top comments (0)