leetcode 669. Trim a Binary Search Tree
LeetCode Tree search Binary trim
2023-09-14 09:11:53 时间
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
解法1:
凡是树的题目无非DFS,BFS,递归或者迭代做,仅此而已。
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def trimBST(self, root, L, R): """ :type root: TreeNode :type L: int :type R: int :rtype: TreeNode """ # use DFS, root first then left and right # if L <= root.val <= R: # new_root with root.val; # new_root.left = self.trimBST(root.left, L, root.val) # new_root.right = self.trimBST(root.right, root.val, R) # return new_root # elif root.val < L: # return self.trimBST(root.right, L, R) # elif root.val > R: # return self.trimBST(root.left, L, R) if root is None: return None if L <= root.val <= R: new_root = TreeNode(root.val) new_root.left = self.trimBST(root.left, L, root.val) new_root.right = self.trimBST(root.right, root.val, R) return new_root elif root.val < L: return self.trimBST(root.right, L, R) elif root.val > R: return self.trimBST(root.left, L, R)
迭代解法:
/** * 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) { if (root == null) { return root; } while (root.val < L || root.val > R) { if (root.val < L) { root = root.right; } if (root.val > R) { root = root.left; } } TreeNode dummy = root; while (dummy != null) { while (dummy.left != null && dummy.left.val < L) { dummy.left = dummy.left.right; } dummy = dummy.left; } dummy = root; while (dummy != null) { while (dummy.right != null && dummy.right.val > R) { dummy.right = dummy.right.left; } dummy = dummy.right; } return root; } }
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- Java实现 LeetCode 542 01 矩阵(暴力大法,正反便利)
- Java实现 LeetCode 513 找树左下角的值
- Java实现 LeetCode 130 被围绕的区域
- Java实现 LeetCode 101 对称二叉树
- Java实现 LeetCode 73 矩阵置零
- 【LeetCode算法-14】Longest Common Prefix
- 【哈希表】leetcode 128. 最长连续序列【中等】
- LeetCode(38): 报数
- LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium
- LeetCode:110_Balanced Binary Tree | 平衡二叉树 | Easy
- [LeetCode] Binary Tree Right Side View
- [LeetCode] Binary Tree Preorder Traversal
- leetcode 518. 零钱兑换 II-----完全背包套路模板
- LeetCode——Binary Tree Level Order Traversal II
- LeetCode——Symmetric Tree
- leetcode第一刷_Validate Binary Search Tree
- leetcode - Convert Sorted List to Binary Search Tree
- leetcode 107. Binary Tree Level Order Traversal II
- leetcode 543. Diameter of Binary Tree
- leetcode 606. Construct String from Binary Tree
- leetcode 784. Letter Case Permutation——所有BFS和DFS的题目本质上都可以抽象为tree,这样方便你写代码
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点