刷题leetcode_669. Trim a Binary Search Tree

Dear 丶 2021-10-09 03:50 209阅读 0赞

二叉搜索树（binary search tree）

## 定义 ##

二叉搜索树：二叉树中任何节点的键值一定大于其左子树中每一个节点的键值，并且小于其右子树中每一个节点的键值。

# 查找 #

基于此，在二叉搜索树中搜索最小元素和最大元素是方便的，从根节点开始，一直往左走，直至无路可走，就得到了最小元素；从跟节点开始，一直往右走，直至无路可走，就得到了最大元素。   
查找任何一个节点也是方便的。从跟节点开始，目标值比当前节点的键值大，就继续往右走，目标值比当前节点的键值小，就继续往左走。

# 插入 #

首先找到合适的位置。从跟节点开始，如果要插入的值比当前节点的键值大，则往右走；如果要插入的值比当前节点的键值小，就往左移动。直到无路可走就找到了插入节点的合适位置。新建一个节点、赋值、插入。

# 删除 #

1、要删除的节点没有子节点。直接删除即可。   
2、要删除的节点只有一个孩子节点。删除后直接将孩子节点连接上即可。例如要删除节点15，删除15后，14成为了13的右节点。   
![这里写图片描述][20150522144703282]   
3、要删除的节点有两个孩子节点。将又子树的最小值替换要删除的节点。例如要删除节点13，用13的右子树中的最小值14替换掉13，然后删除14节点即可。   
![这里写图片描述][20150522145236171]

**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 = 2
    
    Output: 
        1
          \
           2

Example 2:

Input: 
        3
       / \
      0   4
       \
        2
       /
      1
    
      L = 1
      R = 3
    
    Output: 
          3
         / 
       2   
      /
     1

题意：给树的上下界\[L, H\]，节点值在这个范围之内就保留（包括等于），不在范围内就剪枝，返回根节点。

思路：递归

root节点值小于L，删除左节点（抛弃不管了），对右子树剪枝（递归）。

root节点值大于R，删除右节点（抛弃不管了），对左子树剪枝（递归）。

root节点值在L和R之间，左侧对左子子树剪枝（递归）右侧对右子树剪枝（递归）。

/**
     * 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 null;
             if(root.val >= L && root.val <= R) {
                root.left = trimBST(root.left, L, R);
                root.right = trimBST(root.right, L, R);
                return root;
            }
            if(root.val < L)  return trimBST(root.right, L, R);
            if(root.val > R)  return trimBST(root.left, L, R);
        }
    }

[20150522144703282]: /images/20211009/e0adbc8d9858418eb41f1cfa09ee9b3e.png
[20150522145236171]: /images/20211009/070e11cea8634667ab431b3fcc53b0df.png