Java C++ 算法题解leetcode669修剪二叉搜索树示例

问题描述

给定一个二叉搜索树，同时给定区间[L,R]，将BST中所有小于L的节点和大于R的节点剪枝。

解法

题目要求我们剪掉所有小于L的节点和大于R的节点，我们可以采取遍历整个二叉搜索树的方式，检查每个节点是否在指定区间[L,R]内。如果当前节点的值小于L，则需要删除当前节点的左子树中所有节点；如果当前节点的值大于R，则需要删除当前节点的右子树中所有节点；否则继续遍历左右子树。

public TreeNode trimBST(TreeNode root, int L, int R) {
    if (root == null) {
        return null;
    }
    if (root.val < L) {
        return trimBST(root.right, L, R);
    }
    if (root.val > R) {
        return trimBST(root.left, L, R);
    }
    root.left = trimBST(root.left, L, R);
    root.right = trimBST(root.right, L, R);
    return root;
}

TreeNode* trimBST(TreeNode* root, int L, int R) {
    if (root == nullptr) {
        return nullptr;
    }
    if (root->val < L) {
        return trimBST(root->right, L, R);
    }
    if (root->val > R) {
        return trimBST(root->left, L, R);
    }
    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);
    return root;
}

我们先判断当前节点的值是否小于L，这是因为如果节点的值小于L，那么节点的左子树中所有节点的值都会小于L，需要删除左子树的所有节点。因此，我们需要递归删除当前节点的左子树，并将当前节点的右子树作为新的根节点返回。

接下来，我们判断当前节点的值是否大于R，这是因为如果节点的值大于R，那么节点的右子树中所有节点的值都会大于R，需要删除右子树的所有节点。因此，我们需要递归删除当前节点的右子树，并将当前节点的左子树作为新的根节点返回。

如果当前节点的值在[L,R]之间，我们需要继续遍历当前节点的左右子树，并更新其左右子树的指针。

示例说明

假设当前二叉搜索树如下：

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

我们要删除二叉树中所有小于5和大于13的节点。

Java代码如下：

TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.right.right = new TreeNode(14);
root.left.right.left = new TreeNode(4);
root.left.right.right = new TreeNode(7);

Solution solution = new Solution();
TreeNode result = solution.trimBST(root, 5, 13);

System.out.println(result);

运行结果如下：

      8
     / \
    6   10
     \    \
      7    13

C++代码如下：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val < L) {
            return trimBST(root->right, L, R);
        }
        if (root->val > R) {
            return trimBST(root->left, L, R);
        }
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

int main() {
    TreeNode *root = new TreeNode(8);
    root->left = new TreeNode(3);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(6);
    root->right->right = new TreeNode(14);
    root->left->right->left = new TreeNode(4);
    root->left->right->right = new TreeNode(7);

    Solution solution;
    TreeNode *result = solution.trimBST(root, 5, 13);

    cout << result << endl;

    return 0;
}

运行结果如下：

      8
     / \
    6   10
     \    \
      7    13

从结果可以看出，我们成功删除了小于5和大于13的节点，只保留了中间的节点。