Trim a Binary Search Tree
给一个BST, 然后给一个L和R两个整数, 给BST剪枝(trim), 问剪枝后的树. 这个题很有意思, 首先要理解剪枝这个操作, 仅仅是针对当前node的. 而对于node的子树,需要重新判断, 那么这个题就是一个子问题划分的题, 我们要通过递归不断把问题分解. 通过观察example, 我们可以看出, node.val如果大于R, 那么node的右边的子树都大于R, 那么都应该剪掉, 所以返回node的左边, 并且继续子问题探索. 同理对node.val小于R的情况. 如果node.val在L和R之间, 那么我们只需要继续分开讨论左边和右边子问题即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public TreeNode trimBST(TreeNode root, int L, int R) { if(root == null) return null; 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 root; } } } |