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 = 2Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1 L = 1
R = 3Output:
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 null;
root.left = trimBST(root.left,L,R); //递归的删除,从底层删起
root.right = trimBST(root.right,L,R);
if (root.val<L||root.val>R){ //这里是如何删除满足条件的节点的代码
if (root.left!=null&&root.right!=null){
root.val = findMax(root.left).val; //这是有两个孩子的情况
trimBST(root.left,root.val-1,root.val+1);
}
else { //只有一个孩子或无孩子
if (root.left==null)
root = root.right;
else if (root.right==null)
root = root.left;
}
}
return root;
}
public TreeNode findMax(TreeNode root){
if (root==null)
return null;
if (root.right==null)
return root;
else
return findMax(root.right);
}
}