669. 修剪二叉搜索树
题目链接/文章讲解
这道题目比较难，比 添加增加和删除节点难的多，建议先看视频理解。
思路
public class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
//注意，不可以直接if(root > high || root.val < low) return null; 因为可能删除某个节点a，但是节点a的右孩子还在范围内
if (root.val < low) { //小于左边界，但是要删除的节点的右孩子可能符合边界，所以要继续向右遍历
TreeNode right = trimBST(root.right, low, high); // 寻找符合区间[low, high]的节点
return right; //递归向下遍历，子树不符合区间的都会被修剪
}
if (root.val > high) {
TreeNode left = trimBST(root.left, low, high); // 寻找符合区间[low, high]的节点
return left; //如果递归返回null，会返回给移除节点的上一层，就相当于移除了这个节点
}
root.left = trimBST(root.left, low, high); // root.left接入符合条件的左孩子
root.right = trimBST(root.right, low, high); // root.right接入符合条件的右孩子
return root;
}
public static void main(String[] args) {
Solution solution = new Solution();
// 示例测试用例
TreeNode root = new TreeNode(3);
root.left = new TreeNode(0);
root.right = new TreeNode(4);
root.left.right = new TreeNode(2);
root.left.right.left = new TreeNode(1);
int low = 1;
int high = 3;
TreeNode newRoot = solution.trimBST(root, low, high);
printTree(newRoot); // 打印修剪后的树结构
}
// 辅助方法：打印二叉树
public static void printTree(TreeNode root) {
if (root != null) {
printTree(root.left);
System.out.print(root.val + " ");
printTree(root.right);
}
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null) return null;
if(root.val < low){
return trimBST(root.right, low, high);
}
if(root.val > high){
return trimBST(root.left, low, high);
}
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}
108.将有序数组转换为二叉搜索树
思路
- 选取中间节点，递归遍历左右区间，构造左右子树
- 选取中节点，一定要选取中间位置，这样左右区间节点数量才是相同的。
- 如果数组长度是偶数，取靠左右两侧的节点都可以，因为二叉树结构可以不同
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//返回值TreeNode 代表返回构造平衡二叉搜索树的根节点
//左右区间：左闭右闭还是左闭右开？ 这里是左闭右闭
private TreeNode traversal(int[] nums, int left, int right) {
if(left > right) return null;//终止条件
//int mid = (left + right) / 2; //这里可能爆内存 但是本题中left right是数组里的下标，不可能爆内存
int mid = ((right - left)/2) + left;
//构造二叉树
TreeNode root = new TreeNode(nums[mid]);
//递归构造左右子树
root.left = traversal(nums, left, mid - 1);
root.right = traversal(nums, mid + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return traversal(nums, 0, nums.length - 1);
}
}
538.把二叉搜索树转换为累加树
思路
- 后序遍历再从后到前做一个累加。从最大的节点开始遍历：右中左。
- 如何把数值倒序相加：数组里会考虑双指针，一个pre一个cur，cur把pre的数值做一个相加。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int pre = 0; // 记录前一个节点的数值
private void traversal(TreeNode cur){ //因为就是遍历和更新指针数值，所以不需要返回值
if(cur == null) return; //没有返回值
// 右中左遍历
traversal(cur.right);
cur.val += pre;
pre = cur.val;
traversal(cur.left);
}
public TreeNode convertBST(TreeNode root) {
pre = 0;
traversal(root);
return root;
}
}
总结篇
https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html
二刷记得再来总结……
