我們一起聊聊十五周算法—二叉搜索樹（BST）
今天是十五周算法訓練營的第五周，主要講二叉搜索樹專題，包含：驗證二叉搜索樹、不同的二叉搜索樹、二叉樹的最近公共祖先、二叉搜索樹的最近公共祖先。（歡迎加入十五周算法訓練營，與小伙伴一起卷算法）
BST的特性：
對于BST的每一個節(jié)點node，左子樹節(jié)點的值都比node的值要小，右子樹節(jié)點的值都比node的值大；
對于BST的每一個節(jié)點node，它的左側(cè)子樹和右側(cè)子樹都是BST。
BST有一個重要的性質(zhì)：BST的中序遍歷結(jié)果是有序的（升序），也就是在中序位置可以將每個節(jié)點的值升序打印出來
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍歷代碼位置
print(root.val);
traverse(root.right);
}驗證二叉搜索樹
給你一個二叉樹的根節(jié)點 root ，判斷其是否是一個有效的二叉搜索樹。
有效 二叉搜索樹定義如下：
節(jié)點的左子樹只包含 小于 當前節(jié)點的數(shù)。 節(jié)點的右子樹只包含 大于 當前節(jié)點的數(shù)。 所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1：
輸入：root = [2,1,3] 輸出：true
根據(jù)二叉搜索樹特性，通過中序遍歷獲取。
// 解題思路：
// 1. 是否可以通過遍歷一遍二叉樹得到答案？
// 通過中序遍歷可以得到，因為BST的中序遍歷是一個升序結(jié)果
function isValidBST1(root) {
let inorder = -Infinity;
let result = true;
let traverse = root => {
if (root === null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
// 中序位置獲取當前值，并比較其和前一個值的大小，如果小于等于前一個值，則證明不是BST樹，則將結(jié)果變?yōu)閒alse
if (root.val <= inorder) {
result = false;
} else {
inorder = root.val;
}
traverse(root.right);
// 后續(xù)位置
};
traverse(root);
return result;
}
// 將中序遍歷變?yōu)檠h(huán)的方式
function isValidBST2(root) {
if (root === null) {
return true;
}
let head = root;
const stack = [];
let inorder = -Infinity;
// 中序遍歷的循環(huán)結(jié)構(gòu)是需要創(chuàng)建一個棧，然后先將左節(jié)點全壓入棧中
while (stack.length > 0 || head !== null) {
// 當head不為空時，壓入棧中
if (head !== null) {
stack.push(head);
head = head.left;
} else {
// 彈出棧頂元素
head = stack.pop();
if (inorder >= head.val) {
return false;
}
inorder = head.val;
head = head.right;
}
}
return true;
}
// 2. 是否可以定義一個遞歸函數(shù)，通過子問題（子樹）的答案推導出原問題的答案？
// 答案是可以的,因為搜索二叉樹的性質(zhì)是：
// (1)對于BST的每一個節(jié)點node，左子樹節(jié)點值都比node的值要小，右子樹節(jié)點的值逗比node的值大；
// (2)對于BST的每一個節(jié)點node，它的左側(cè)子樹和右側(cè)子樹都是BST
// 則我們解決該問題可定義一個遞歸函數(shù)來進行解決
// 注意：該問題需要借助外部變量，因為根節(jié)點的值必須大于左子樹所有值、小于右子樹所有值，所以需要引入最大最小值
function isValidBST3(root) {
// 構(gòu)造一個輔助函數(shù)，判斷根節(jié)點是否在（min，max）范圍內(nèi)
const helper = (root, min, max) => {
if (root === null) {
return true;
}
if (root.val <= min) {
return false;
}
if (root.val >= max) {
return false;
}
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
};
// 初始狀態(tài)min為-Infinity，max為Infinity
return helper(root, -Infinity, Infinity);
}不同的二叉搜索樹
給你一個整數(shù) n ，求恰由 n 個節(jié)點組成且節(jié)點值從 1 到 n 互不相同的 「二叉搜索樹」 有多少種？返回滿足題意的二叉搜索樹的種數(shù)。
示例 1：」
輸入：n = 3
輸出：5
利用的也是左子樹值 < 根節(jié)點 < 右子樹值
// 對于BST的每一個節(jié)點node，左子樹節(jié)點的值都比node的值要小，右子樹節(jié)點的值都比node的值大
// 在該問題中，1~n都有可能成為根節(jié)點，然后左邊的是左子樹上的點，右邊的是右子樹上的點，然后對應(yīng)根節(jié)點的搜索樹數(shù)量就是左子樹的組合數(shù) * 右子樹的組合數(shù)；
// 該問題明顯就轉(zhuǎn)換為一個遞歸問題
function numTree(n) {
// 為了解決子問題的重復問題，需要引入備忘錄
const memo = [];
for (let i = 0; i < n + 1; i++) {
memo.push([]);
for (let j = 0; j < n + 1; j++) {
memo[i].push(0);
}
}
const count = (low, high) => {
// 遞歸終止條件
if (low > high) {
return 1;
}
// 判斷備忘錄中是否存在該值，存在的話直接使用
if (memo[low][high] > 0) {
return memo[low][high];
}
let result = 0;
for (let i = low; i <= high; i++) {
const left = count(low, i - 1);
const right = count(i + 1, high);
result += left * right;
}
// 將結(jié)果存儲到備忘錄中
memo[low][high] = result;
return result;
};
return count(1, n);
}
console.log(numTree(3));二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節(jié)點 p、q，最近公共祖先表示為一個節(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
示例 1：
輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 輸出：3 解釋：節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3 。
// 通過遞歸解決（后續(xù)遍歷）
function lowestCommonAncestor(root, p, q) {
// 確定遞歸函數(shù)
const traverse = (node, p, q) => {
// 確定遞歸終止條件
if (node === null || node === p || node === q) {
return node;
}
const left = traverse(node.left, p, q);
const right = traverse(node.right, p, q);
// 后續(xù)位置
// 找到一個節(jié)點，其發(fā)現(xiàn)p、q節(jié)點分別出現(xiàn)在其左右子樹上
if (left !== null && right !== null) {
return node;
}
// p或q本身就是最近公共祖先
if (left === null) {
return right;
}
return left;
};
return traverse(root, p, q);
}二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。
// 因為是二叉搜索樹，其是有順序的，所以找最近公共祖先節(jié)點的問題就轉(zhuǎn)換成了該節(jié)點在[p, q]中間即可
function lowestCommonAncestor(root, p, q) {
const helper = (node, p, q) => {
if (node === null) {
return node;
}
if (node.val > p.val && node.val > q.val) {
const left = helper(node.left, p, q);
if (left !== null) {
return left;
}
}
if (node.val < p.val && node.val < q.val) {
const right = helper(node.right, p, q);
if (right !== null) {
return right;
}
}
return node;
};
return helper(root, p, q);
}
