内容简介：给定二叉搜索树以及例 :采用深度优先遍历, 如果当前节点的值, 在区间内, 则正常返回, 如果不在区间内, 则将当前节点删除, 并将左子树或右子树嫁接到当前节点.
给定二叉搜索树以及 L
和 R
最低和最高边界作为修剪树，使其所有元素都在[L, R]（R> = L）. 您可能需要更改树的根，因此结果应返回修剪后的二叉搜索树的新根。
例 :
给予树:
1
/ \
0 2
L = 1
R = 2
输出:
1
\
2
给予树:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
输出:
3
/
2
/
1
解法
采用深度优先遍历, 如果当前节点的值, 在区间内, 则正常返回, 如果不在区间内, 则将当前节点删除, 并将左子树或右子树嫁接到当前节点.
/**
* 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;
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
if (root.val <= R && root.val >= L) return root;
if (root.val < L) {
return root.right;
} else {
return root.left;
}
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Trim a Binary Search Tree. Memory Usage: 36.9 MB, less than 98.26% of Java online submissions for Trim a Binary Search Tree.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Pro CSS and HTML Design Patterns
Michael Bowers / Apress / April 23, 2007 / $44.99
Design patterns have been used with great success in software programming. They improve productivity, creativity, and efficiency in web design and development, and they reduce code bloat and complexit......一起来看看 《Pro CSS and HTML Design Patterns》 这本书的介绍吧!
