Follow

Follow

·Apr 15, 2022·

# 669. Trim a Binary Search Tree

## 題目敘述

Given the `root` of a binary search tree and the lowest and highest boundaries as `low` and `high`, trim the tree so that all its elements lies in `[low, high]`. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1:

``````Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
``````

Example 2:

``````Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]
``````

Constraints:

• The number of nodes in the tree in the range `[1, 104]`.
• `0 <= Node.val <= 10**4`
• The value of each node in the tree is unique.
• `root` is guaranteed to be a valid binary search tree.
• `0 <= low <= high <= 10**4`

## 解法解析

### 解法範例

#### Go

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func trimBST(root *TreeNode, low int, high int) *TreeNode {
if root == nil {
return nil
} else if root.Val < low {
return trimBST(root.Right, low, high)
} else 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
}
``````

#### JavaScript

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} low
* @param {number} high
* @return {TreeNode}
*/
var trimBST = function (root, low, high) {
if (!root) 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;
};
``````

#### Kotlin

``````/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
*     var left: TreeNode? = null
*     var right: TreeNode? = null
* }
*/
class Solution {
fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
return if (root == null) {
null
} else if (root.`val` < low) {
trimBST(root.right, low, high)
} else if (root.`val` > high) {
trimBST(root.left, low, high)
} else {
root.left = trimBST(root.left, low, high)
root.right = trimBST(root.right, low, high)
root
}
}
}
``````

#### PHP

``````/**
* Definition for a binary tree node.
* class TreeNode {
*     public \$val = null;
*     public \$left = null;
*     public \$right = null;
*     function __construct(\$val = 0, \$left = null, \$right = null) {
*         \$this->val = \$val;
*         \$this->left = \$left;
*         \$this->right = \$right;
*     }
* }
*/
class Solution
{

/**
* @param TreeNode \$root
* @param Integer \$low
* @param Integer \$high
* @return TreeNode
*/
function trimBST(\$root, \$low, \$high)
{
if (\$root == null) {
return null;
}
if (\$root->val < \$low) {
return \$this->trimBST(\$root->right, \$low, \$high);
}
if (\$root->val > \$high) {
return \$this->trimBST(\$root->left, \$low, \$high);
}
\$root->left = \$this->trimBST(\$root->left, \$low, \$high);
\$root->right = \$this->trimBST(\$root->right, \$low, \$high);
return \$root;
}
}
``````

#### 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: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
def trim(node):
if node is None:
return node
elif node.val > high:
return trim(node.left)
elif node.val < low:
return trim(node.right)
else:
node.left = trim(node.left)
node.right = trim(node.right)
return node

return trim(root)
``````

#### Rust

``````// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn trim_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> Option<Rc<RefCell<TreeNode>>> {
if let Some(node_ref) = root {
let mut node = node_ref.borrow_mut();
if node.val > high {
return Self::trim_bst(node.left.clone(), low, high);
} else if node.val < low {
return Self::trim_bst(node.right.clone(), low, high);
}
node.left = Self::trim_bst(node.left.clone(), low, high);
node.right = Self::trim_bst(node.right.clone(), low, high);
Some(node_ref.clone())
} else {
None
}
}
}
``````

#### Swift

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     public var val: Int
*     public var left: TreeNode?
*     public var right: TreeNode?
*     public init() { self.val = 0; self.left = nil; self.right = nil; }
*     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
*     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
*         self.val = val
*         self.left = left
*         self.right = right
*     }
* }
*/
class Solution {
func trimBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> TreeNode? {
guard let root = root else {
return nil
}
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
}
}
``````