資訊專欄INFORMATION COLUMN
Problem
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
Solution
Recursive
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null || L > R) return null;
if (root.val > R) return trimBST(root.left, L, R);
if (root.val < L) return trimBST(root.right, L, R);
if (root.val >= L && root.val <= R) {
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
}
return root;
}
}
Iterative
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72068.html
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：題目要求檢驗(yàn)二叉查找樹(shù)是否符合規(guī)則。二叉查找樹(shù)是指當(dāng)前節(jié)點(diǎn)左子樹(shù)上的值均比其小，右子樹(shù)上的值均比起大。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過(guò)研究中序遍歷是否遞增來(lái)判斷二叉查找樹(shù)是否符合規(guī)則。 題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...
摘要：題目要求檢驗(yàn)二叉查找樹(shù)是否符合規(guī)則。二叉查找樹(shù)是指當(dāng)前節(jié)點(diǎn)左子樹(shù)上的值均比其小，右子樹(shù)上的值均比起大。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過(guò)研究中序遍歷是否遞增來(lái)判斷二叉查找樹(shù)是否符合規(guī)則。 題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...
摘要：題目要求判斷一個(gè)樹(shù)是否是二叉查找樹(shù)。二叉查找樹(shù)即滿足當(dāng)前節(jié)點(diǎn)左子樹(shù)的值均小于當(dāng)前節(jié)點(diǎn)的值，右子樹(shù)的值均大于當(dāng)前節(jié)點(diǎn)的值。思路一可以看到，對(duì)二叉查找樹(shù)的中序遍歷結(jié)果應(yīng)當(dāng)是一個(gè)遞增的數(shù)組。這里我們用堆棧的方式實(shí)現(xiàn)中序遍歷。 題目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...
摘要：注意這里的結(jié)構(gòu)和不同的二叉樹(shù)遍歷一樣，如果到空節(jié)點(diǎn)就返回，否則遞歸遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節(jié)點(diǎn)大于上限返回假如果該節(jié)點(diǎn)小于下限返回假遞歸判斷左子樹(shù)和右子樹(shù) Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...
閱讀 2595·2021-10-25 09:45
閱讀 1254·2021-10-14 09:43
閱讀 2310·2021-09-22 15:23
閱讀 1538·2021-09-22 14:58
閱讀 1944·2019-08-30 15:54
閱讀 3554·2019-08-30 13:00
閱讀 1367·2019-08-29 18:44
閱讀 1580·2019-08-29 16:59
