9.树
一.BiNode
1.题目描述：
二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
注意：本题相对原题稍作改动
2.示例：
输入： [4,2,5,1,3,null,6,0]//输入是将二叉树以数组的形式表示的，即从上到下从左到右依次填入数组中
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
3.解:
（1）我的答案：
class Solution {
private TreeNode tempPre = null;
private TreeNode head = null;
public TreeNode convertBiNode(TreeNode root) {
if (root == null) return null;
midTravel(root);
return head;
}
public void midTravel(TreeNode root) {
//左节点递归
if (root.left != null) midTravel(root.left);
//对当前节点的操作
//获取新树的头节点，以及初次绑定tempPre
if (root.left == null && tempPre == null) {
head = root;
tempPre = root;
} else {
tempPre.right = root;
root.left = null;
tempPre = root;
}
//右节点递归
if (root.right != null) midTravel(root.right);
}
}（2）网友答案：
public TreeNode convertBiNode(TreeNode root) {
TreeNode head = new TreeNode(0);// 单链表的头指针哨兵
TreeNode prev = head;// 移动的链表前置指针
// 开始中序遍历
TreeNode node = root;
Deque<TreeNode> stack = new LinkedList<>();
while (node != null || !stack.isEmpty()){
if (node != null){
stack.push(node);
node = node.left;
}else {
node = stack.pop();
// ---链表处理
node.left = null;// 左指针置空
prev.right = node;// 右指针作为链表的next指针
prev = node;// 指针后移
// ---链表处理
// 中序遍历进入右子树
node = node.right;
}
}
return head.right;
}4.总结
以上一种是使用递归，一种是非递归，非递归的方式采用栈这种数据结构，看代码即可看懂。
二.二叉搜索树的最近公共祖先-i
1.题目描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
2.示例：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
3.解:
（1）网友答案：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root.val>p.val&&root.val>q.val) return lowestCommonAncestor(root.left,p,q);
if(root.val<p.val&&root.val<q.val) return lowestCommonAncestor(root.right,p,q);
return root;
}
}class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
# 如果当前节点为空，就返回空
if not root:
return None
# 如果当前结点就是p或者q，就返回当前节点
if root in [p, q]:
return root
# 分别去左右子树里面去找
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# 如果左右子树里各有一个p或者q，那么当前就是最前结点
if left and right:
return root
# 如果都在左边，那就是当前这个左边的
elif left:
return left
# 要么就是右边的
elif right:
return right
return None4.总结
简洁明了，利用二叉搜索树的性质，即每个节点的值必须大于等于其左节点的值且必须小于等于其右节点的值。因此就可以使用前，中，后序遍历其中一种进行递归，循环查找，直到找到目标节点。网友1的答案使用的是后序遍历。
第二个答案同样也是对的，这种方法既适用于搜索二叉树，也适用于普通的二叉树。该方法不再是通过节点的值来决定，接下来往左边还是右边走。而是每到一个节点，左右两条路都走，然后每条路会返回一个节点，如果某条路中走下去可以找到p和q其中一个，（当然也存在p和q都可以找到的情况，那样的话目标节点就在当前节点内了）那么该条路就是有返回值的，然后若两条路都有返回值，那么这个节点就是目标节点。单反有一条路没有返回值，那么目标节点一定比当前节点的层数高。
三.将二叉搜索树变平衡
1.题目描述：
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，请你返回任意一种。
2.示例：
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
3.解：
（1）我的答案：
class Solution {
List<TreeNode> newTree = new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
if (root == null) return null;
else midTravel(root);
return rebuild(0, newTree.size() - 1);
}
private void midTravel(TreeNode root) {
if (root.left != null) midTravel(root.left);
newTree.add(root);
if (root.right != null) midTravel(root.right);
}
private TreeNode rebuild(int low, int high) {
if(high < low) return null;
int mid = low + ((high - low) >> 1);
TreeNode root = newTree.get(mid);
root.left = rebuild(low, mid - 1);
root.right = rebuild(mid + 1, high);
return root;
}
}（2）网友答案：
class Solution {
private final int[] array = new int[100001];
private int arrayIndex = 0;
public TreeNode balanceBST(TreeNode root) {
midTraverse(root);
return build(0, arrayIndex - 1);
}
public void midTraverse(TreeNode cur) {
if (cur == null) {
return;
}
midTraverse(cur.left);
array[arrayIndex++] = cur.val;
midTraverse(cur.right);
}
public TreeNode build(int left, int right) {
int mid = left + ((right - left) >> 1);//相当于 left + (right - left) / 2 不写成（left+right）/2是为了防止（left+right）溢出
TreeNode cur = new TreeNode(array[mid]);
if (left < mid) {
cur.left = build(left, mid - 1);
}
if (mid < right) {
cur.right = build(mid + 1, right);
}
return cur;
}
}4.总结
先将每个节点存储到一个链式结构中，然后用二分查找，找到链式结构中最中间位置的元素作为重构树的根节点，然后分别在左半部分和右半部分递归重构该根节点的左右子树，直到重构完成。
四. 二叉搜索子树的最大键值和
1.题目描述：
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
任意节点的左子树中的键值都 小于 此节点的键值。
任意节点的右子树中的键值都 大于 此节点的键值。
任意节点的左子树和右子树都是二叉搜索树。
2.示例：
输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。
输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。
示例 3：
输入：root = [-4,-2,-5]
输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。
3.解
（1）我的答案：
class Solution {
private int result = Integer.MIN_VALUE;
public int maxSumBST(TreeNode root) {
if (root == null) return 0;
subTravel(root);
return result < 0 ? 0 : result;
}
private int[] subTravel(TreeNode root) {
if (root == null) return new int[]{1, 0, Integer.MIN_VALUE, Integer.MAX_VALUE};//位置2代表该树所有节点的最大值，位置3代表。。最小值
int[] left = subTravel(root.left);
int[] right = subTravel(root.right);
int[] temp = new int[4];
if (left[0] == 1 && right[0] == 1 && left[2] < root.val && right[3] > root.val) {
temp[0] = 1;
temp[1] = left[1] + right[1] + root.val;
if (right[2] == Integer.MIN_VALUE && right[3] == Integer.MAX_VALUE) temp[2] = root.val;
else temp[2] = right[2];
if (left[2] == Integer.MIN_VALUE && left[3] == Integer.MAX_VALUE) temp[3] = root.val;
else temp[3] = left[3];
result = Math.max(result, temp[1]);
}
return temp;
}
}4.总结：
没有必要遍历两次，（遍历两次的做法是，建立一个HashMap<TreeNode,int[3]>第一次遍历获取每个节点的总值和最大值，最小值。第二次遍历判断每个节点作根节点的树是否是二叉搜索树（通过判断两个子树是不是二叉搜索树，并判断节点值小于左子树最大值且小于右子树最小值来确定当前节点作根节点的树是不是二叉树），是的话就更新结果最大值。最后两次遍历完之后，返回结果最大值）一次遍历即可。只需要令递归函数的返回值是一个长度为4的数组就行，这4个元素分别存储：节点的总值/所有子节点和自身节点中的最大值/所有子节点和自身节点中的最小值/是不是二叉搜索树。其中一个细节是，若子树为空，则也创建一个长度为4的数组，仿佛有子树一样。
查看6道真题和解析