1 递归
注意，这里的核心思路不是剪枝或者显示删除每个不符合条件的节点。而是通过找到符合条件的节点或者子树，然后把符合条件的拼接到一起，从而间接达到修剪的目的。
根据BST性质，左必然小，右必然大，因此可以先通过节点的值比较找到符合[low, high]区间的节点，然后把两两符合条件的节点进行连接，从而间接移除了不符合条件的节点。
代码语言：javascript复制/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (!root) return nullptr;
// 1.1 在右子树中寻找符合区间[low, high]的节点
if (root->val < low) return trimBST(root->right, low, high);
// 1.2 在左子树中寻找符合区间[low, high]的节点
if (root->val > high) return trimBST(root->left, low, high);
// 2.1 root->left接入符合条件的左子树
root->left = trimBST(root->left, low, high);
// 2.2 root->right接入符合条件的右子树
root->right = trimBST(root->right, low, high);
return root;
}
};
2 迭代法
迭代法略有复杂，等二刷的时候在整啦~
致谢
感谢「代码随想录」公众号梳理的思路，欢迎大家关注这位大佬的公号
