网站如何使用cdn,桂林象鼻山公园,企业网站展示,道路建设网站专题修剪二叉搜索树 题目描述递归代码演示#xff1a; 题目描述 难度 - 中等 LC - 669. 修剪二叉搜索树 给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留… 修剪二叉搜索树 题目描述递归代码演示 题目描述 难度 - 中等 LC - 669. 修剪二叉搜索树 给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。 示例1 提示 树中节点数在范围 [1, 10^4] 内 0 Node.val 10^4 树中每个节点的值都是 唯一 的 题目数据保证输入是一棵有效的二叉搜索树 0 low high 10^4 递归 由于被修剪的是二叉搜索树因此修剪过程必然能够顺利进行。 容易想到使用原函数作为递归函数 若 root.val 小于边界值 low则 root 的左子树必然均小于边界值我们递归处理 root.right 即可若 root.val 大于边界值 high则 root 的右子树必然均大于边界值我们递归处理 root.left 即可若 root.val 符合要求则 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;* }* }*/
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.right trimBST(root.right,low,high);root.left trimBST(root.left,low,high);return root;}
}
