Talking Recursively Part II :
Complete Binary Tree & Binary Search Tree
这篇文章相较于Part I 而言会通过题目展示完全二叉树和二叉搜索树的性质。
题目列表
完全二叉树
二叉查找树
完全二叉树和满二叉树
满二叉树
首先先介绍一下满二叉树的概念
在图中可以看到，满二叉树除了叶子节点之外，其余的所有节点都有两个子节点。
完全二叉树
一棵深度为h的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
完全二叉树则其中有一部分是满二叉树，并且最后一层的节点需要连续集中在左侧。
很显然满二叉树是完全二叉树的一个特例。
小根堆
如果将一个完全二叉树按照层次遍历的顺序标记每个节点，我们不难发现，每一个父节点的值小于两个子节点的值。
如果将这个完全二叉树按照层次遍历的方式进行序列化，可以得到一个数组，对于这个数组中的下标为i的个体，他的值（用value(i)）表示，是小于value(2i)和value(2i+1)的。
所以对于一个这样标记过的完全二叉树，对于节点值为i的元素进行（i/2）向下取整就可以找到父节点的值。
二叉树寻路
利用这个性质可以完成二叉树寻路这道题。
本文的解法来源来自于这篇题解，二叉树寻路，下面我结合这篇原文的思想说的更清楚一点。
对于一个编号完全的满二叉树（就像上面的图一样），将偶数行进行翻转，就成了下面的二叉树（下面的图）。
对于数组反转的策略，我们通常使用数组两侧对调位置（轴对称翻转）的策略来实现：
所以很明显，原本在满二叉树
i的父节点x会被进行轴对称翻转到另外一侧。但是尽管做了翻转，上图中对应颜色的两个数字加起来的值是相等的（因为是按照顺序编号），所以这个公式应该成立：
但是Java中没有提供直接的log2函数，这个地方可以使用换底公式。将公式写成代码如图：
class Solution {
public List<Integer> pathInZigZagTree(int label) {
LinkedList<Integer> result= new LinkedList<>();
int N = (int) (Math.log(label) / Math.log(2)) + 1;
while(label > 1){
result.add(label);
N--;
label = (int) (3 * Math.pow(2, N - 1) - label/ 2- 1);
}
result.add(1);
Collections.reverse(result);
return result;
}
}
完全二叉树的结点个数
-
完全二叉树的节点个数
使用上一节讲过的『要素分析法』： - 子问题： 对于子树root的节点个数等于左子树的节点个数+右子树的节点个数
- 递归出口：对于root == null时 return 0
- 返回值： 表示节点root的节点数量
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = countNodes(root.left);
int right = countNodes(root.right);
return left + right + 1;
}
}
我也就写到了上面这里，真正好的思路的题解来自这里：
这样的代码对于任何一棵树root都是可行的，完全没有使用到完全二叉树的性质。
因为完全二叉树是将节点从左向右放置的（最后一行），因此可以满足如图的性质：
- 当左子树的深度和右子树相等时：
说明左子树一定是满二叉树，右子树是否是完全二叉树不知道。 - 当左子树的深度和右子树不相等时：
左子树不一定是满二叉树，但是右子树一定是满二叉树。
对于求深度，这里也不需要使用递归的策略，因为是满二叉树，所以先填充左侧，通过一直看左子树的深度就知道整棵树的深度了，代码如下：
class Solution {
private int depth(TreeNode root){
int depth = 0;
TreeNode node = root;
while(node != null) {
node = node.left;
depth++;
}
return depth;
}
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = depth(root.left);
int right= depth(root.right);
if(left == right) {
//左子树数量 + 节点 + 右子树
return (1 << left ) + countNodes(root.right);
}else{
//右子树数量 + 节点 + 左子树
return (1 << right) + countNodes(root.left);
}
}
}
二叉查找树
二叉查找树可以说是数据结构中非常优美和工整的一类了，它的定义是这样的：
对于树root，他的左子树的所有节点全部小于root的value，右子树的所有节点值大于root的value。
二叉查找树的英文名字是：Binary Search Tree，这个名字一看就有一种『二分查找』的意思，确实，二叉查找树的主要功能就是提供一个非常方便的二分搜索。
二叉搜索树的基本性质
二叉搜索树中的搜索
先通过一个题快速了解二叉搜索树：
返回值： 如果存在这个节点，返回这个节点对应的Treenode
子问题：对于节点root，如果root的value等于给定值，返回root，如果小于给定值，在树的右边继续搜索，如果大于给定值，在树的左边继续搜索。
递归出口：当root为空时返回null，表示这个树root不存在给定值对应的节点。
很显然，这个题是一个遍历结构的问题，可以直接使用遍历模板：
class Solution {
//带有返回值的递归搜索
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) return root;
return root.val < val ? searchBST(root.right,val) :searchBST(root.left, val);
}
}
合法二叉搜索树
这个题本身实际上是对二叉树的定义的一个巩固：
-
验证二叉搜索树
二叉搜索树的定义在更深的层面上揭示了一棵树root的左右子树要满足一个数量区间的约束关系，这道题思路比较简单，直接上代码：
public class 验证二叉搜索树 {
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root,Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean validate(TreeNode node, long min, long max){
if(node == null) return true;
if(node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) && validate(node.right,node.val,max);
}
}
}
二叉搜索树的构建
二叉搜索树还有一个非常好的性质，二叉搜索树的中序遍历是有序的。下面看看两个和有序数列相关的二叉搜索树问题：
将有序链表转换为二叉搜索树
这个问题在最开始讲链表的总结的时候讲过，当时只是当做一个快慢指针的应用讲的，这次我们从递归以及构建二叉平衡搜索树的角度来看看这道题。
之前说过，二叉平衡搜索树的定义是这样的：对于树root，其左子树和右子树的节点绝对值差不超过2（可以等于0、1）并且需要是一个二叉搜索树。 因此我们需要从链表的中间节点下手来构建这棵二叉平衡搜索树：
- 返回值： 需要返回最终构成的节点
- 子问题：将mid的左边作为左子树，将mid的右边作为右子树
-
递归出口：当链表head为空，或者mid等于head时（此时说明链表已经被分解成了惟一的节点，可以作为一一颗子树了）
代码如下：
class Solution {
public ListNode findMiddleElement(ListNode node){
ListNode prev = null;
ListNode slow = node;
ListNode fast = node;
while(fast != null && fast.next != null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
if(prev != null) prev.next = null;
return slow;
}
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
ListNode mid = findMiddleElement(head);
if(mid == head) return new TreeNode(mid.val);
TreeNode midTreeNode = new TreeNode(mid.val);
midTreeNode.left = sortedListToBST(head);
midTreeNode.right = sortedListToBST(mid.next);
return midTreeNode;
}
}
二叉树的修剪
修剪二叉搜索树
-
修剪二叉搜索树
对于这道题，可能一上来就回考虑到删除是否要包含根节点的问题，如果两者不分开考虑的话很容易掉进分析的误区，这里不妨将是否包含根节点分解成两个子问题来看：
分解成两个子问题
- 删除不包含根节点
假设删除不包含根节点，则删除时：
- 返回值：返回删除完成之后的子树
- 子问题：节点root的value 小于删除下界，说明待删除都聚集在root的右边，继续删除右子树；root的value大于上界说明待删除都聚集在root的左边。
- 递归出口：这个明显有一个遍历树的特征，当root为空时，返回null
这样的三个步骤是否也适用于包含根节点的情况呢？很显然，确实！
对于图二的情况，只要左移到左子树，之后返回以3为根节点的子树就可以了：
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if(root == null) return null;
if(root.val < L) return trimBST(root.right, L, R);
if(root.val > R) return trimBST(root.left, L, R);
root.left = trimBST(root.left, L, R);
root.right= trimBST(root.right,L, R);
return root;
}
}
这道题和我们之前写过的带有返回值的递归函数有点点不同，以往写的递归函数，如斐波拉契数列，求树的深度，尾递归调用了两个递归函数，求他们之间的一个数量关系，所以整体来看，这样的递归函数的返回值并不是自身计算的结果，下面用一个形象的图展示：
所以在最后验证的时候，不需要有过多的顾虑。
删除二叉搜索树中的节点
-
删除二叉搜索树中的节点
二叉搜索树还有一个非常重要的性质：二叉搜索树的中序遍历是一个有序的序列。节点node 在中序遍历之后的序列中的前面一个节点称为它的前驱节点，后面的节点称为它的后继节点。
前驱和后继
如果需要删除二叉搜索树的节点的话，需要保证删除完成的中序遍历也是有序的。那也就是说，可以使用这个被删除的节点的前驱和后继顶上。
这道题对于不同种类的节点的删除操作是不一样的，我们不妨通过枚举法枚举所有的情况
- 叶子节点，直接删除
-
只有一个孩子：
2.1 只有左孩子：
只有左孩子
可以使用前驱代替。
为什么不使用后继节点呢？因为后继节点大于当前的值，一定在序列的后面，根据中序遍历来说，这个值在该节点的右子树或者父节点或者，该节点不存在右子树，找父节点也不方便。
2.2 只有右孩子：
只有右孩子
同理，需要使用后继代替。 - 有两个孩子：
那就随便使用前驱还是后继了。
如何找前驱和后继
对于节点root，他的前驱应该小于root的value，但是需要是小于中的最大的，所以这个节点应该在root的左子树的最右边；同理可以找到后继节点。
代码如下：
class Solution {
private int forward(TreeNode node){
node = node.left;
while(node.right!= null) node = node.right;
return node.val;
}
private int backward(TreeNode node){
node = node.right;
while(node.left != null) node = node.left;
return node.val;
}
public TreeNode deleteNode(TreeNode node, int key) {
//需要
//为什么需要： 是中序遍历的出口
if(node == null) return null;
if(key > node.val) node.right = deleteNode(node.right, key);
else if(key < node.val) node.left = deleteNode(node.left, key);
else{
if(node.left == null && node.right == null) node = null;
else if(node.right == null){
node.val = forward(node);
node.left = deleteNode(node.left, node.val);
}else{
node.val = backward(node);
node.right = deleteNode(node.right, node.val);
}
}
return node;
}
}
