代码随想录算法训练营day23 | 题目669、题目108、题目109、题目538
题目一描述
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
提示：
树中节点数在范围 [1, 10^4] 内
0 <= Node.val <= 10^4
树中每个节点的值都是 唯一 的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 10^4
解题思路
后序遍历，重建整棵树即可。
代码实现
方法一：
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null)
return null;
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
if (root.val > high) {
return root.left;
}
if (root.val < low) {
return root.right;
}
return root;
}
}
题目二描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列
解题思路
通过数组构建二叉树就是用递归，不断寻找区间然后返回结点到左右子树上。基本都是前序遍历。
这涉及到结点之间的连接问题，所以是不断返回到左右子树重建。
代码实现
方法一：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length);
}
private TreeNode build(int[] nums, int left, int right) {
if (left >= right)
return null;
int index = (right - left) / 2;
if (right - left == 1)
return new TreeNode(nums[index]);
TreeNode root = new TreeNode(nums[index]);
root.left = build(nums, left, index);
root.right = build(nums, index + 1, right);
return root;
}
}
题目三描述
给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
示例 1:
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = []
输出: []
提示:
head 中的节点数在[0, 2 * 10^4] 范围内
-10^5 <= Node.val <= 10^5
解题思路
与数组的类似，需要有一个找链表中结点的过程，注意传参的范围也要更改。
代码实现
方法一：
class Solution {
public TreeNode sortedListToBST(ListNode head) {
return build(head, null);
}
private TreeNode build(ListNode head, ListNode end) {
if (head == end) // 注意这里的终止条件是end
return null;
ListNode mid = getMidNode(head, end);
TreeNode root = new TreeNode(mid.val);
root.left = build(head, mid);
root.right = build(mid.next, end);
return root;
}
private ListNode getMidNode(ListNode head, ListNode end) {
ListNode slow = head;
ListNode fast = head;
while (fast != end && fast.next != end) { // 注意这里的终止条件是end
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
题目四描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：
树中的节点数介于 0 和 10^4 之间。
每个节点的值介于 -10^4 和 10^4 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
解题思路
注意想清楚结点的操作顺序，操作顺序正好就是先右子树的中序遍历。
这里不涉及到子树的重建，所以不需要左右子树连接递归函数。
也不涉及到需要左右子树的信息，所以不是后序遍历，信息自底向上传递。
想清楚操作在哪里处理，然后再使用这样的顺序递归。
代码实现
方法一：
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null)
return null;
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);
return root;
}
}
