修剪二叉搜索树
问题：
思路：
分治递归：
递归函数的功能是使以当前节点为根的树修剪完毕且返回处理完成后的树根节点
当根节点的值小于下界时，根节点以及其左子树应全部丢弃，此时返回对根节点的右孩子递归调用函数的返回值。当根节点的值大于上界时，根节点以及其右子树应全部丢弃，此时返回对根节点的左孩子递归调用函数的返回值。
若根节点的值处于下界与上界之间，分别对根节点的左右子树进行递归函数调用，其返回值作为根节点的左右孩子，最后返回根节点。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if( root==NULL )
return root;
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;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153860.html
