Ming

Posted on

# 代码随想录day21 | 530. Minimum Absolute Difference in BST, 501. Find Mode in BST, 236. Lowest Common Ancestor of a Binary Tree

## leetcode 530 - Minimum Absolute Difference in BST

``````//👍 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

example:

``````//👍 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

• 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
• 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的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);
};

``````

1. BST常用in-order dfs
2. 寻找公共祖先要用post-order dfs