java数据结构与算法刷题-----LeetCode669. 修剪二叉搜索树

本文主要是介绍java数据结构与算法刷题-----LeetCode669. 修剪二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

文章目录

- 1. 递归
- 2. 迭代

解题思路

二叉搜索树，当前结点左边都比它小，右边都比它大
所以我们前序遍历

如果当前结点node，比low小，说明它和左子树都小于low，抛弃，那么剩下右子树保留，使用同样的套路判断，因为右子树都比node大，无法确定是否抛弃
如果node比high大，抛弃右子树，左子树保留进行判断。

1. `递归`

代码：时间复杂度O(n),空间复杂度O(n)

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;int val = root.val;//如果当前结点<low，说明它和它的左子树都小于low，都需要去掉//但是右子树都比当前结点大，不能直接去掉，需要继续递归单独也判断一下if(val < low) return trimBST(root.right,low,high);//如果val<low，抛弃左子树，递归右子树，并返回右子树递归结果else if(root.val > high) return trimBST(root.left,low,high);//如果val>high，抛弃右子树，递归左子树else {//如果当前结点在low和high之间，说明其需要保留，则继续递归判读子孙是否需要去除root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}}
}
/*** 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;*     }* }*/

2. `迭代`

代码：时间复杂度O(n),空间复杂度O(1)

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {//找到第一个不需要抛弃的结点，作为根结点。while (root != null && (root.val < low || root.val > high)) {//如果root不为null,并且root是要抛弃的结点就向下遍历if (root.val < low) {root = root.right;} else {root = root.left;}}if (root == null) {//如果这个根结点为null，说明所以结点都需要抛弃，返回null即可return null;}//将比low小的抛弃for (TreeNode node = root; node.left != null; ) {//从root开始遍历if (node.left.val < low) {//如果左子树left比low小，node.left = node.left.right;//抛弃left和其左子树，保留右子树} else {//如果左子树left比low大，那么right肯定更大，所以只需要继续向左找，因为左边是更小的值，才有可能小于lownode = node.left;}}//将比high大的抛弃for (TreeNode node = root; node.right != null; ) {if (node.right.val > high) {//比high大node.right = node.right.left;//抛弃其本身和其右子树，保留左子树} else {node = node.right;}}return root;}
}