这是悦乐书的第284次更新，第301篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第152题（顺位题号是669）。给定二叉搜索树以及L和R的最低和最高边界，修剪树以使其所有元素位于[L，R]（R> = L）。可能需要更改树的根，因此结果应返回修剪后的二叉搜索树的新根。例如：
输入：L = 1 R = 2
1
/ \
0 2
输出：
1
\
2
输入：L = 1 R = 3
3
/ \
0 4
\
2
/
1
输出：
3
/
2
/
1
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
使用递归的方式。因为是二叉搜索树，并且返回的新二叉树的根节点值是未定的，需要先确定根节点在哪，确定完根节点后，再去确定它的左子树和右子树。如果当前节点值比右边界要大，那么新节点只可能在左子树那边；如果当前节点值比左边界还要小，那么新节点只能在右子树那边。剩下就是正常情况，新左节点还是在左边，新右节点还是在右边。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return null;
}
if (root.val > R) {
return trimBST(root.left, L, R);
}
if (root.val < L) {
return trimBST(root.right, L, R);
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
}
03 第二种解法
使用迭代的方式。首先，还是需要确定根节点在哪里，使用一个循环来判断，如果当前节点值大于右边界，就往左子树里面找，如果小于左边界，就往右子树里面找。接着，从确定好的根节点开始，处理它的左子树，还是还是用循环，如果当前节点不为空，并且它的左节点本身也不为空，它的左节点值小于左边界，那么就跟换它的左节点，将当前节点的左节点重新指向到当前节点左节点的右子节点。同理，对于右子树的处理也是一样的逻辑，只是将判断换成了大于右边界值。最后返回新的二叉树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) {
return null;
}
// 先确定根节点的位置
while (root.val > R || root.val < L) {
if (root == null) {
return null;
}
if (root.val > R) {
root = root.left;
}
if (root.val < L) {
root = root.right;
}
}
// 处理左子树
TreeNode temp = root;
while (temp != null) {
// 如果当前节点的左节点不为空且节点值小于左边界
while (temp.left != null && temp.left.val < L) {
// 就将当前节点的左节点指向当前节点左节点的右子节点
temp.left = temp.left.right;
}
temp = temp.left;
}
// 处理右子树
temp = root;
while (temp != null) {
// 如果当前节点的右节点不为空且节点值大于右边界
while (temp.right != null && temp.right.val > R) {
// 就将当前节点的右节点指向当前节点右节点的左子节点
temp.right = temp.right.left;
}
temp = temp.right;
}
return root;
}
}
04 小结
算法专题目前已日更超过四个月，算法题文章152+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！