Welcome to Subscribe On Youtube
-
/** Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree. Example 1: Input: 1 / \ 0 2 L = 1 R = 2 Output: 1 \ 2 Example 2: Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 Output: 3 / 2 / 1 */ public class Trim_a_Binary_Search_Tree { /* Input: 1 / \ 0 2 L = 0 R = 0 Output: 0 */ /** * 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) { // basic rule: if root is deleted, the move right to be new root if (root == null) { return null; } if (root.val < L) { // then all its left children are less than L, only return right child root = trimBST(root.right, L, R); } else if (root.val > R) { // then all its right children bigger than R, and disgarded root = trimBST(root.left, L, R); } else { root.left = trimBST(root.left, L, R); root.right = trimBST(root.right, L, R); } return 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 root; } if (root.val > high) { return trimBST(root.left, low, high); } if (root.val < low) { return trimBST(root.right, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } }
-
// OJ: https://leetcode.com/problems/trim-a-binary-search-tree/ // Time: O(N) // Space: O(logN) class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if (!root) return nullptr; 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; } };
-
# 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 dfs(root): if root is None: return root if root.val > high: return dfs(root.left) if root.val < low: return dfs(root.right) root.left = dfs(root.left) root.right = dfs(root.right) return root return dfs(root) ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode: if not root: return None if L > root.val: return self.trimBST(root.right, L, R) elif R < root.val: return self.trimBST(root.left, L, R) root.left = self.trimBST(root.left, L, R) root.right = self.trimBST(root.right, L, R) return root
-
/** * 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 root } if root.Val > high { return trimBST(root.Left, low, high) } if root.Val < low { return trimBST(root.Right, low, high) } root.Left = trimBST(root.Left, low, high) root.Right = trimBST(root.Right, low, high) return root }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function trimBST( root: TreeNode | null, low: number, high: number, ): TreeNode | null { const dfs = (root: TreeNode | null) => { if (root == null) { return root; } const { val, left, right } = root; if (val < low || val > high) { return dfs(left) || dfs(right); } root.left = dfs(left); root.right = dfs(right); return root; }; return dfs(root); }
-
/** * 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) { function dfs(root) { if (!root) { return root; } if (root.val < low) { return dfs(root.right); } if (root.val > high) { return dfs(root.left); } root.left = dfs(root.left); root.right = dfs(root.right); return root; } return dfs(root); };
-
// 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( mut root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32, ) -> Option<Rc<RefCell<TreeNode>>> { if root.is_none() { return root; } { let mut node = root.as_mut().unwrap().borrow_mut(); if node.val < low { return Self::trim_bst(node.right.take(), low, high); } if node.val > high { return Self::trim_bst(node.left.take(), low, high); } node.left = Self::trim_bst(node.left.take(), low, high); node.right = Self::trim_bst(node.right.take(), low, high); } root } }
-
/** * 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) { while (root != null && root.val < L) root = root.right; if (root == null) return null; TreeNode parentLeft = root, childLeft = root.left; while (childLeft != null) { if (childLeft.val < L) { parentLeft.left = childLeft.right; childLeft = childLeft.right; } else { parentLeft = childLeft; childLeft = childLeft.left; } } while (root != null && root.val > R) root = root.left; if (root == null) return null; TreeNode parentRight = root, childRight = root.right; while (childRight != null) { if (childRight.val > R) { parentRight.right = childRight.left; childRight = childRight.left; } else { parentRight = childRight; childRight = childRight.right; } } return 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 root; } if (root.val > high) { return trimBST(root.left, low, high); } if (root.val < low) { return trimBST(root.right, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } }
-
// OJ: https://leetcode.com/problems/trim-a-binary-search-tree/ // Time: O(N) // Space: O(logN) class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if (!root) return nullptr; 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; } };
-
# 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 dfs(root): if root is None: return root if root.val > high: return dfs(root.left) if root.val < low: return dfs(root.right) root.left = dfs(root.left) root.right = dfs(root.right) return root return dfs(root) ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def trimBST(self, root: TreeNode, L: int, R: int) -> TreeNode: if not root: return None if L > root.val: return self.trimBST(root.right, L, R) elif R < root.val: return self.trimBST(root.left, L, R) root.left = self.trimBST(root.left, L, R) root.right = self.trimBST(root.right, L, R) return root
-
/** * 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 root } if root.Val > high { return trimBST(root.Left, low, high) } if root.Val < low { return trimBST(root.Right, low, high) } root.Left = trimBST(root.Left, low, high) root.Right = trimBST(root.Right, low, high) return root }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function trimBST( root: TreeNode | null, low: number, high: number, ): TreeNode | null { const dfs = (root: TreeNode | null) => { if (root == null) { return root; } const { val, left, right } = root; if (val < low || val > high) { return dfs(left) || dfs(right); } root.left = dfs(left); root.right = dfs(right); return root; }; return dfs(root); }
-
/** * 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) { function dfs(root) { if (!root) { return root; } if (root.val < low) { return dfs(root.right); } if (root.val > high) { return dfs(root.left); } root.left = dfs(root.left); root.right = dfs(root.right); return root; } return dfs(root); };
-
// 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( mut root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32, ) -> Option<Rc<RefCell<TreeNode>>> { if root.is_none() { return root; } { let mut node = root.as_mut().unwrap().borrow_mut(); if node.val < low { return Self::trim_bst(node.right.take(), low, high); } if node.val > high { return Self::trim_bst(node.left.take(), low, high); } node.left = Self::trim_bst(node.left.take(), low, high); node.right = Self::trim_bst(node.right.take(), low, high); } root } }