LeetCode 二叉查找树(BST)
这里的函数是有返回值的,不是void型,所以需要注意的是:(在代码中已经标注)
/** * 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* insertIntoBST(TreeNode* root, int val) { if(root==NULL){//递归边界 root=new TreeNode(val); return root; } if(val==root->val){//查找成功,说明结点已经存在,直接返回 return root; } else if(root->val<val) root->right=insertIntoBST(root->right,val);//必须是这样(必须赋值给root->right),不能是直接insertIntoBST() else root->left=insertIntoBST(root->left,val);//必须是这样,不能是insertIntoBST() return root; } };
《实验楼》:
题解 - 递归
二叉树的题使用递归自然是最好理解的,代码也简洁易懂,缺点就是递归调用时栈空间容易溢出,故实际实现中一般使用迭代替代递归,性能更佳嘛。不过迭代的缺点就是代码量稍(很)大,逻辑也可能不是那么好懂。
既然确定使用递归,那么接下来就应该考虑具体的实现问题了。在递归的具体实现中,主要考虑如下两点:
- 基本条件/终止条件 - 返回值需斟酌。
- 递归步/条件递归 - 能使原始问题收敛。
首先来找找递归步,根据二叉查找树的定义,若插入节点的值若大于当前节点的值,则继续与当前节点的右子树的值进行比较;反之则继续与当前节点的左子树的值进行比较。题目的要求是返回最终二叉搜索树的根节点,从以上递归步的描述中似乎还难以对应到实际代码,这时不妨分析下终止条件。
有了递归步,终止条件也就水到渠成了,若当前节点为空时,即返回结果。问题是——返回什么结果?当前节点为空时,说明应该将「插入节点」插入到上一个遍历节点的左子节点或右子节点。对应到程序代码中即为root->right = node
或者root->left = node
. 也就是说递归步使用root->right/left = func(...)
即可。
因为正确答案的格式是这样的。所以必须要保存目标节点的父节点和前驱结点的父节点。
感觉《算法笔记》中的代码不可行。
算法代码参考的课本
/** * 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* deleteNode(TreeNode* root, int key) {//删除以root为根节点的树中权值为x的结点 TreeNode *p,*f,*s,*q; p=root;f=NULL; while(p){//查找值为key的结点p,p的前驱为f if(p->val==key) break; f=p; if(p->val>key) p=p->left; else p=p->right; } if(p==NULL) return root;//如果没有值为key的结点 if(p->left==NULL){//p没有左子树的情况 if(f==NULL){ root=p->right;//根结点就是要找的p结点 } else if(f->left==p){ f->left=p->right; } else{ f->right=p->right; } } else{//p有左子树,找p的前驱 q=p;//q是前驱的父亲节点 s=p->left; while(s->right){//跳出这个循环后,s就指向了前驱结点,q则指向了s的父节点 q=s; s=s->right; } if(p==q){ q->left=s->left; } else{ q->right=s->left; } p->val=s->val; } return root; } };
有一点需要注意:总是优先删除前驱(或者后继)容易导致树的左右子树高度极度不平衡。使得二叉树退化成一条链。解决这一问题的办法有两种:一种是每次交替删除前驱或后继;另一种是记录树的高度,总是优先在高度较高的一颗子树里删除结点。
思路:从上到下,如果一直true,则最终为true。如果有一个为false,则直接返回false。
如果要是迭代的话,从根节点开始,判断有无左右子树,最终循环结束的条件为:左右子树都没有孩子结点的时候跳出循环。中途若没有false。则最终返回true。
用辅助栈来实现吧。我觉得既然能用栈,就可以用递归吧。
没有考虑到这种情况。卧槽,我发现自己的代码的普适性太低了。只能适用于很少的例子。其实还是没有考虑周全。掌握本质
自己只是考虑到了当前根节点的左右孩子节点的关系。并没有注意到从第一个根节点就必须建立起:左边的树的任何结点都必须小于第一个根节点的概念(右边的树的任何结点都要大于第一个根节点)。
自己的错误代码:
/** * 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: bool isValidBST(TreeNode* root) { stack<TreeNode*> stk; if(root==NULL) return false; stk.push(root); if(!(root->left||root->right)) return true; TreeNode* temp=root; while(temp&&(temp->left||temp->right)&&!stk.empty()){ temp=stk.top(); stk.pop(); if(temp->right&&temp->right->val>temp->val){//如果有右孩子,且右孩子值大于根 stk.push(temp->right); if((temp->right->val)<(temp->val)){//如果右孩子值小于根{ break; } } else if(temp->left&&temp->left->val<temp->val){//如果有左孩子,且左孩子值小于根 stk.push(temp->left); if((temp->left->val)>(temp->val))//如果左孩子值大于根 break; } } if(temp&&temp->right&&(temp->right->val)<(temp->val)){ return false; } else if(temp&&temp->left&&(temp->left->val)>(temp->val)){ return false; } else return true; } };
/** * 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: bool isValidBST(TreeNode* root) { stack<TreeNode*> stk; TreeNode *pre,*temp; temp=root;pre=NULL; if(temp==NULL) return true; while(true){ while(NULL!=temp){//先把所有的左子树从上到下依次入栈 stk.push(temp); temp=temp->left; } if(stk.empty()){ break; } temp=stk.top(); stk.pop(); if(pre!=NULL&&temp&&pre->val>=temp->val){ return false; } pre=temp; if(temp&&temp->right){ temp=temp->right; } else temp=NULL; } return true; } };