遇到二叉搜索树请记住，中序遍历是有序数组！！！左右根
二叉搜索树中的搜索
js
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
js
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var searchBST = function (root, val) {
if (!root) return null;
if (root.val === val) return root;
else if (val > root.val) return searchBST(root.right, val);
else return searchBST(root.left, val);
};
验证二叉搜索树
leetcode: 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
思路：二叉搜索树的中序遍历是从小到大的， 左右根
js
var isValidBST = function (root) {
// 二叉搜索树的中序遍历是从小到大的
function inorder(node) {
if (!node) return [];
return [...inorder(node.left), node.val, ...inorder(node.right)];
}
let arr = inorder(root);
for (let i = 1; i < arr.length; i++) {
if (arr[i] <= arr[i - 1]) return false;
}
return true;
};
优化 递归 提前减少遍历！
js
var isValidBST = function (root) {
// 二叉搜索树的中序遍历是从小到大的
let pre = -Infinity;
function check(node) {
if (!node) return true;
// check left
let left = check(node.left);
// check current
if (node.val < pre) return false;
pre = node.val;
// check right
let right = check(node.right);
return left && right;
}
return check(root);
};
二叉搜索树的最小绝对差
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
提示：树中至少有 2 个节点。
js
var getMinimumDifference = function (root) {
function inorderLoop(node) {
if (!node) return [];
return [...inorderLoop(node.left), node.val, ...inorderLoop(node.right)];
}
let inorder = inorderLoop(root);
let min = Infinity;
for (let i = 1; i < inorder.length; i++) {
min = Math.min(min, inorder[i] - inorder[i - 1]);
}
return min;
};
二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],
js
输入：root = [1,null,2,2]
输出：[2]
js
var findMode = function (root) {
let map = {};
function dfs(node) {
if (!node) return;
dfs(node.left);
dfs(node.right);
if (!map[node.val]) map[node.val] = 1;
else map[node.val]++;
}
dfs(root);
const max = Math.max(...Object.values(map));
return Object.keys(map).filter((key) => map[key] === max);
};
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内
todo...
把二叉搜索树转换为累加树
leetcode 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
BST 的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.
js
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var convertBST = function (root) {
let num = 0;
function dfs(node) {
if (!node) return null;
dfs(node.right);
node.val = node.val + num;
num = node.val;
dfs(node.left);
return node;
}
return dfs(root);
};