669. Trim a Binary Search Tree 修剪二叉搜索树 Java
题目要求对一棵二叉搜索树进行规定的修剪：剪去小于x的，大于y的。
我们只需要递归地对树的左子树右子树进行修剪即可。
所有情况如下：
- 根root的值不在（x，y）内，则判断是小于x还是大于y，分别返回右子树的修剪和左子树的修剪（因为如果root小于x，那么它的左子树必定都小于x，所以我们只需考虑它的右子树。root大于y同理。）
- root的值在（x，y）内：
- 对root的左子树进行同样的修剪，并把结果返回，赋给root的左子树，成为root的新左子树
- 对root的右子树进行同样的修剪，并把结果返回，赋给root的右子树，成为root的新右子树
- root为空null，说明树的结构不再延续，要返回null
/** * 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 < L) return trimBST(root.right, L, R); if(root.val > R) return trimBST(root.left, L, R); root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); return root; } }