这篇文章共享一个 2022 年考研的数据结构标题：
有两棵非空二叉树 T1，T2。二叉树的存储结构式都是线性存储:

const T1 = [40, 25, 60, -1, 30, -1, 80, -1, -1, 27];
const T2 = [40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35];

请设计一个算法，判别 T1 和 T2 是否为查找二叉树

线性存储，一般依照层次遍历的次序存储，先将二叉树的第一层放到数组的第 0 个方位，然后将第二层放到数组的第 1 第 2 个方位；然后将第三层放到数组的第 3，4，5，6 个方位，依次类推，假如遇到节点为空的状况，就将节点的值置为-1

判别一颗树是否为查找二叉树，有一个判别标准，便是每个节点都大于左子树的一切节点，且都小于右子树的一切节点。

说着简单，可是要怎样做呢？对于每一个节点都求一遍左右子树的最大最小节点吗？能够换个视点求解。从叶子节点开始核算左子树的最大节点，和右子树的最小节点。然后把核算结果给叶子节点的父节点，这样父节点就获得了以自己作为根节点的树的最大值和最小值。

假如这个父节点的父节点想要最大值仍是最小值，都没有问题。依次类推，由下而上，层层递进，就能够判别以任意节点作为根节点的子树是否为查找二叉树。

代码

const judgeBiSearchTree2 = (data) => {
	const min = [...data];
	const max = [...data];
	for (let i = data.length - 1; i > 0; i--) {
		if (data[i] == -1) continue;
		const parentIndex = Math.floor((i - 1) / 2);
		if (i % 2 == 1 && data[parentIndex] > max[i]) min[parentIndex] = min[i];
		else if (i % 2 == 0 && data[parentIndex] < min[i]) max[parentIndex] = max[i];
		else return false;
	}
	return true;
};

用次序结构作为二叉树的存储结构，根和左右子树满意这样的一个联系：

  • 假定节点在数组中的下标是 i，那么左节点的下标便是 2i+1，右节点的下标便是 2i+2；所以左节点的下标一定是奇数，右节点是偶数。

所以代码中使用i % 2 == 1和i % 2 == 0 来判别节点是左节点仍是右节点。

  • 假定节点在数组中的下标是 i，那么节点的父节点的下标便是Math.floor((i - 1) / 2)。这个在纸上画个二叉树就能理解了

代码逻辑：

  1. 先初始化两个数组，min 和 max，min 表明一个节点所代表的子树的最小值；max 表明一个节点所代表的子树的最大值。
  2. 从 data 数组的后面往前遍历，即从叶子节点向上遍历
  3. 开始遍历。先获取父节点的下标
  4. 假如当时节点是父节点的左节点，就用父节点和当时节点的所代表的最大值比较，假如大于，就满意二叉查找树的定义。并且更新父节点的最小值。由于一个节点所代表子树的最小值肯定是来自这个节点的左子树
  5. 假如当时节点是父节点的右节点，就用父节点和当时节点的所代表的最小值比较，假如小于，就满意二叉查找树的定义。并且更新父节点的最大值。由于一个节点所代表子树的最大值肯定是来自这个节点的右子树
  6. 假如走到了第三个 else，那就阐明这个节点不契合二叉查找树的定义了，直接回来 false
  7. 假如遍历顺利走完了，阐明每个节点都满意二叉查找树，就回来 true 吧

测验代码：

const printBiTree = (data, index = 0) => {
	if (data[index] == -1 || index >= data.length) return;
	printBiTree(data, index * 2 + 1);
	console.log(data[index]);
	printBiTree(data, index * 2 + 2);
};
const T1 = [40, 25, 60, -1, 30, -1, 80, -1, -1, 27];
const T2 = [40, 50, 60, -1, 30, -1, -1, -1, -1, -1, 35];
printBiTree(T1);
// 25
// 27
// 30
// 40
// 60
// 80

二叉查找树有个性质，左节点 < 当时节点 < 右节点，这就意味着二叉查找树的中序遍历是一个升序序列。我们能够通过输出的序列，人眼判别这棵树是否为二叉查找树

上面的输出是升序序列没问题

console.log(judgeBiSearchTree(T1));
// true

和人眼判别共同，没有问题。

修正 T1 数组：

const T1 = [40, 25, 60, -1, 30, -1, 80, -1, -1, 99]; // 27 -> 99
printBiTree(T1);
// 25
// 99
// 30
// 40
// 60
// 80
console.log(judgeBiSearchTree(T1)); 
false

将 T1 数组中最终一个值换成了 99，中序遍历不再是升序序列了，并且judgeBiSearchTree的回来值也就变成了 false

解法二

上面提到了使用中序遍历，用人眼辅助判别代码编写是否正确。其实这道题的解法，也能够使用中序遍历来解决。

我们能够在中序遍历的进程中，就直接判别遍历到的序列是否是一个升序序列。来看看怎样完成吧

let num = -1;
const judgeBiSearchTree2 = (data, index = 0) => {
	if (data[index] == -1 || index >= data.length) return true;
	if (judgeBiSearchTree(data, index * 2 + 1) == false) return false;
	if (num < data[index]) num = data[index];
	else return false;
	if (judgeBiSearchTree(data, index * 2 + 2) == false) return false;
	return true;
};

在函数的外面声明晰一个 num，来存储上一个遍历到的数据。在遍历进程，会将遍历到的数据和 num 进行比较，假如大于 num，那就更新 num，继续往后遍历；假如小于 num，阐明这次遍历到的数据小于上一次遍历到的数据，即遍历序列不是升序序列，也就意味着这棵树不是二叉查找树。

思维便是这样，代码逻辑也是这样，很简单，直接来看测验代码

const T1 = [40, 25, 60, -1, 30, -1, 80, -1, -1, 27];
const T1_2 = [40, 25, 60, -1, 30, -1, 80, -1, -1, 99];
printBiTree(T1);
console.log(judgeBiSearchTree2(T1));
// 25
// 27
// 30
// 40
// 60
// 80
// true
printBiTree(T1_2);
console.log(judgeBiSearchTree2(T1_2));
// 25
// 99
// 30
// 40
// 60
// 80
// false

测验结果契合预期，代码没有问题

总结

这篇文章共享了两种方法来判别一颗树是否为平衡二叉树，代码简单清晰，测验进程详实，逻辑严谨，是个不可多得的好文章。下篇文章继续共享更多好的算法小操练

你觉得这篇文章怎样样？我每天都会共享一篇算法小操练，喜欢就点赞+关注吧