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.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:
Input: 
    1
   / \ 
  0   2 
  L = 1
  R = 2
Output: 
    1 
      \ 
       2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example 2: 
Input:  
    3 
   / \ 
  0  4 
   \
    2
   / 
  1 
  L = 1
  R = 3
Output:  
		3 
     /  
   2    
  / 
 1

题目大意

保留二叉树内值为[L, R]之间的节点

解题思路

递归
寻找值在[L, R]之间的节点，修建其左右子树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
     func trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
        guard let tree = root else { return nil }
        if tree.val < L {
            return trimBST(tree.right, L, R)
        }else if tree.val > R{
            return trimBST(tree.left, L, R)
        }
        tree.left = trimBST(tree.left, L, R)
        tree.right = trimBST(tree.right, L, R)
        return tree
    }
}
0%