669. Trim a Binary Search Tree - Easy
Given a binary search tree and the lowest and highest boundaries as? 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 ? M1: recursion 如果root.val比R大,说明要trim掉右边的节点,要返回的subtree在root的左边,即递归到root.left; 如果root.val比L小,说明要trim掉左边的节点,要返回的subtree在root的右边,递归到root.right; 如果root.val在[L,R],说明有可能左右两边都需要trim,分别递归左右节点 time: O(n),space: O(height) /** * 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 > R) { return trimBST(root.left,L,R); } if(root.val < L) { return trimBST(root.right,R); } root.left = trimBST(root.left,R); root.right = trimBST(root.right,R); return root; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |