题目地址(669. 修剪二叉搜索树)

https://leetcode-cn.com/problems/trim-a-binary-search-tree/

题目描述

  1. 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
  3. 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
  7. 示例 1：
  9. 输入：root = [1,0,2], low = 1, high = 2
  10. 输出：[1,null,2]
  13. 示例 2：
  15. 输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
  16. 输出：[3,2,null,1]
  19. 示例 3：
  21. 输入：root = [1], low = 1, high = 2
  22. 输出：[1]
  25. 示例 4：
  27. 输入：root = [1,null,2], low = 1, high = 3
  28. 输出：[1,null,2]
  31. 示例 5：
  33. 输入：root = [1,null,2], low = 2, high = 4
  34. 输出：[2]
  39. 提示：
  41. 树中节点数在范围 [1, 104] 内
  42. 0 <= Node.val <= 104
  43. 树中每个节点的值都是唯一的
  44. 题目数据保证输入是一棵有效的二叉搜索树
  45. 0 <= low <= high <= 104

前置知识


公司

  • 暂无

思路

  1. root.val < lo，这种情况下 root 节点本身和 root 的左子树全都是小于 lo 的，都需要被剪掉。
  2. root.val > hi，这种情况下 root 节点本身和 root 的右子树全都是大于 hi 的，都需要被剪掉。

    关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode trimBST(TreeNode root, int low, int high) {
  19.             //递归中止条件
  20.             if (root == null) {
  21.                 return null;
  22.             }
  23.             //在区间外 删除小于low的节点的左子树 大于high的节点的右子树
  24.             if (root.val < low) {
  25.                 //如果root小于low 就删除左子树以及他本身 也就是直接返回右子树的节点
  26.                 return trimBST(root.right, low, high);
  27.             }
  28.             if (root.val > high) {
  29.                 //同样的 如果root大于high 就删除右子树以及他本身 也就是直接返回左子树的节点
  30.                 return trimBST(root.left, low, high);
  31.             }
  32.             //在区间内 什么都不干 继续递归
  33.             root.left = trimBST(root.left, low, high);
  34.             root.right = trimBST(root.right, low, high);
  35.             return root;
  36.         }
  37.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：669. 修剪二叉搜索树 - 图1#card=math&code=O%28n%29&id=IoVCu)
  • 空间复杂度：669. 修剪二叉搜索树 - 图2#card=math&code=O%28n%29&id=SPB04)