LeetCode 二叉查找树（BST)

/**
 * 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;
    }
};

/**
 * 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;
    
    }     
};

/**
 * 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;
    }
};