530. 二叉搜索树的最小绝对差
题目：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例：
输入：root = [4,2,6,1,3]
输出：1
解题思路：
二叉搜索树的中序遍历是有序的，因此可以使用双指针来依次记录最小值。
var getMinimumDifference = function (root) {
let result = Infinity;
let pre = null;
const traversal = (cur) => {
if (cur === null) {
return;
}
traversal(cur.left);
if (pre !== null) {
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
traversal(cur.right);
}
traversal(root);
return result;
};
501. 二叉搜索树中的众数
题目：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
-
左子树和右子树都是二叉搜索树
示例：
输入：root = [1,null,2,2]
输出：[2]
解题思路：
这道题依然是利用双指针中序遍历来解决。
var findMode = function (root) {
let pre = null;
let count = 0;
let maxCount = 0;
let result = [];
const traversal = (cur) => {
if (cur === null) {
return;
}
traversal(cur.left);
if (pre === null) {
count = 1;
} else if (pre.val === cur.val) {
count++;
} else {
count = 1;
}
pre = cur;
if (count === maxCount) {
result.push(cur.val)
}
if (count > maxCount) {
maxCount = count;
result = [];
result.push(cur.val);
}
traversal(cur.right);
}
traversal(root);
return result;
};
236. 二叉树的最近公共祖先
题目：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
解题思路：
这道题是从下往上遍历所以采用后序遍历。判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q和p的最近祖先。
var lowestCommonAncestor = function (root, p, q) {
const traversal = (root, p, q) => {
if (!root) {
return root;
}
if (root === p || root === q) {
return root;
}
const left = traversal(root.left, p, q);
const right = traversal(root.right, p, q);
if (left !== null && right !== null) {
return root;
}
if (left === null && right !== null) {
return right;
}
else if (left !== null && right === null) {
return left;
} else {
return null;
}
}
return traversal(root, p, q);
};
