leetCode题解之修剪二叉查找树

1、题目描述

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.

题目的意思是给定一个二叉查找树，和两个值。删除掉树中所有不在两个值范围内的节点。

2、题目分析

由于二叉查找树的递归定义和数据有序的特点，使用递归方法解决二叉查找树是比较理想的。

3、代码

 1 TreeNode* trimBST(TreeNode* root, int L, int R) {
 2         
 3         if( root == NULL )
 4             return NULL;
 5         
 6         if( root->val < L  )
 7         {
 8              return trimBST(root->right,L,R);
 9         }
10         
11         if(root->val > R )
12         {
13             return trimBST(root->left,L,R);
14         }
15         
16         root->left = trimBST(root->left,L,R);
17         root->right = trimBST(root->right,L,R);
18            
19         return root;
20         
21     }