669. Trim a Binary Search Tree

669. Trim a Binary Search Tree

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 \

Example 2: Input:

\ 0 4 \

思路： 考虑到二叉搜索树的特性，根的值肯定大于左结点的值，肯定大于右结点的值。可以利用递归的思想。 判断root的值是否在[L,R]范围内 root.val小于L的值，则直接舍弃左子树，返回继续修剪以root.right为根结点的右子树； root.val大于R的值，则直接舍弃右子树，返回继续修剪以root.left为根结点的左子树； 在范围内，则继续修剪左子树和右子树，然后返回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) { if(root == null) return root; if(root.val < L){ return trimBST(root.right,L,R); } else if(root.val > R){ return trimBST(root.left,L,R); } else{ root.left = trimBST(root.left,L,R); root.right = trimBST(root.right,L,R); return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。