思路： 每次先判断根节点是否为空，为空直接返回，否则就判断根节点的值，在范围内就分别对左右子树进行判断，否则，例如根节点值小于L，那么这个结点左边所有的子树都不需要再判断了，因为这是二叉搜索树，根节点左边所有结点的值都小于该根节点的值
递归就完事了
#include<iostream> #include<cstdlib> using namespace std; typedef struct TreeNode { int val; TreeNode *left; TreeNode *right; } TreeNode,*SearchTree,*Position; void PreOrderTraversal(SearchTree T) { if(T==NULL) return; cout<<T->val<<" "; PreOrderTraversal(T->left); PreOrderTraversal(T->right); } SearchTree Insert(int val,SearchTree T) { if(T==NULL) { T = (SearchTree)malloc(sizeof(TreeNode)); if(T==NULL) { cout<<"MALLOC ERROR\n"<<endl; exit(1); } T->val = val; T->left = T->right = NULL; } else { if(val>T->val) T->right = Insert(val,T->right); else if(val<T->val) T->left = Insert(val,T->left); } return T; } class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if(root==NULL) return NULL; else if(root->val>= L && root->val<=R) { root->left = trimBST(root->left,L,R); root->right = trimBST(root->right,L,R); return root; } else return root->val<L ? trimBST(root->right,L,R):trimBST(root->left,L,R); } }; int main() { Solution s; SearchTree T1 = NULL; SearchTree T2 = NULL; T1 = Insert(3,T1); T1 = Insert(0,T1); T1 = Insert(4,T1); T1 = Insert(2,T1); T1 = Insert(1,T1); // T1 = Insert(6,T1); // T1 = Insert(9,T1); PreOrderTraversal(T1); cout<<endl; T2 = s.trimBST(T1,1,3); PreOrderTraversal(T2); return 0; }