LeetCode.669.Trim a Binary Search Tree 修剪二叉搜索树BST

题目描述

669 Trim a Binary Search Tree https://leetcode-cn.com/problems/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 = 2

Output:
    1
      \
       2

Example 2:

Input:
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output:
      3
     /
   2
  /
 1

解题过程

修剪二叉搜索树 BST，递归求解

• 根小于左界，剪掉根及左子树
• 根大于右届，剪掉根及右子树
• 根在左右届之间，分别修剪其左右子树

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (null == root) {
            return root;
        }
        if (root.val < L) {
            // 根小于左界，剪掉根及左子树
            return trimBST(root.right, L, R);
        }
        if (root.val > R) {
            // 根大于右届，剪掉根及右子树
            return trimBST(root.left, L, R);
        }
        if (root.val >= L && root.val <= R) {
            root.right = trimBST(root.right, L, R);
            root.left = trimBST(root.left, L, R);
        }
        return root;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_669_TrimBinarySearchTree.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_669_TrimBinarySearchTree.java