题目
给你二叉搜索树的根节点 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]
示例 3：
输入：root = [1], low = 1, high = 2 输出：[1]
示例 4：
输入：root = [1,null,2], low = 1, high = 3 输出：[1,null,2]
示例 5：
输入：root = [1,null,2], low = 2, high = 4 输出：[2]
解答
方法一：递归
如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode: if not root: return root if root.val < low: return self.trimBST(root.right,low,high) # 寻找符合区间[low, high]的节点 if root.val > high: return self.trimBST(root.left,low,high) # 寻找符合区间[low, high]的节点 root.left = self.trimBST(root.left,low,high) # root->left接入符合条件的左孩子 root.right = self.trimBST(root.right,low,high) # root->right接入符合条件的右孩子 return root
c++解法
class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(!root) return root; 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; } };
java解法
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; } }
