[数据结构与算法]2021-09-13 -14二叉搜索树

二叉搜索树中的搜索

特点有序

递归法

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
		if(root==NULL||root->val==val){//终止条件
			return root;
		}
		if(root->val > val){
			return searchBST(root->left,val);//小于就搜索左子树
		}
		if(root->val < val){
			return searchBST(root->right,val);
		}
		return NULL;
    }
};

迭代法

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
		while(root){
			if(root->val > val){
				root=root->left;
			}
			else if(root->val < val){
				root=root->right;
			}
			else{
				return root;
			}	
		}
		return NULL;
    }
};

验证二叉搜索树

class Solution {
public:
    void traversal(TreeNode* root,vector<int>& tree){
    	if(root==NULL){
    		return;
		}
		traversal(root->left,tree);
		tree.push_back(root->val);
		traversal(root->right,tree);
	}
	bool isValidBST(TreeNode* root) {
		vector<int> tree;
		traversal(root,tree);
		for(int i=1;i<tree.size();i++){
			if(tree[i]<=tree[i-1]){
				return 0;
			}
		}
		return 1;
    }
};

class Solution {
public:
	TreeNode* pre=NULL;
	bool isValidBST(TreeNode* root) {
		if(root==NULL){
			return 1;
		}
		bool left=isValidBST(root->left);
		if(pre!=NULL&&pre->val>=root->val){
			return 0;
		} 
		pre=root;//每一轮最终的pre是右结点 
		bool right=isValidBST(root->right);
		return left&&right;
    }
};

二叉搜索树的最小绝对差

class Solution {
public:
	int res=INT_MAX;
	TreeNode* pre;
	void traversal(TreeNode* cur){
		if(cur==NULL){
			return ;
		}
		traversal(cur->left);
		if(pre!=NULL){
			res=min(res,cur->val-pre->val);
		}
		pre=cur;
		traversal(cur->right);
	}
    int getMinimumDifference(TreeNode* root) {
		traversal(root);
		return res;
    }
};

二叉搜索树中的众数

class Solution {
public:
	int maxC=0;
	int count=0;
	TreeNode* pre=NULL;
	vector<int> res;
	void searchBST(TreeNode* cur){
		if(cur==NULL){
			return;
		}
		searchBST(cur->left);//左
		if(pre==NULL){//中
			count=1;
		}
		else if(pre->val==cur->val){
			count++;
		}
		else{
			count=1;
		}
		pre=cur;
		if(count==maxC){
			res.push_back(cur->val);
		}
		if(count>maxC){
			maxC=count;
			res.clear();
			res.push_back(cur->val);
		}
		searchBST(cur->right);//右
		return;
	}
    vector<int> findMode(TreeNode* root) {
		res.clear();
		searchBST(root);
		return res;
    }
};x

二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==q||root==p||root==NULL){
			return root;
		}
		TreeNode* left=lowestCommonAncestor(root->left,p,q);
		TreeNode* right=lowestCommonAncestor(root->right,p,q);
		if(left!=NULL&&right!=NULL){
			return root;
		}
		if(left==NULL){
			return right;
		}
		return left;//包含NULL和left
	}
};

二叉搜索树的最近公共祖先

递归法，不考虑NULL

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if(root->val > p->val&&root->val > q->val){
			return lowestCommonAncestor(root->left,p,q);
		}
		else if(root->val < p->val&&root->val < q->val){
			return lowestCommonAncestor(root->right,p,q);
		}
		else{
			return root;
		}
	}
};

迭代，效率高

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } 
            else if (root->val < p->val && root->val < q->val) {
                root = root->right;
            }
            else return root;
        }
        return NULL;
    }
};

二叉搜索树中的插入操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
		if(root==NULL){
			TreeNode* node=new TreeNode(val);
			return node;
		}
		if(root->val > val){
			root->left=insertIntoBST(root->left,val);
		}
		if(root->val < val){
			root->right=insertIntoBST(root->right,val);
		}
		return root;
    }
};

删除二叉搜索树中的节点

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
		if(root==NULL){//没找到返回空
			return root;
		}
		if(root->val==key){
			if(root->left==NULL){//左右都为空包含在这个判断
				return root->right;
			}
			else if(root->right==NULL){
				return root->left;
			}
			else{//左右都不为空
				TreeNode* cur=root->right;
				while(cur->left!=NULL){
					cur=cur->left;
				}
				cur->left=root->left;
				TreeNode* tmp=root;
				root=root->right;
				delete tmp;
				return root;
			}
		}
		if(root->val>key){//接住下层返回的新结点
			root->left=deleteNode(root->left,key);
		}
		if(root->val<key){
			root->right=deleteNode(root->right,key);
		}
		return root;
    }
};

修剪二叉搜索树

递归

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
		if(root==NULL){
			return root;
		}
		if(root->val < low){
			return trimBST(root->right,low,high);//删除操作，将左子结点的右子结点返回，因为它的val可能大于low
		}
		if(root->val > high){
			return trimBST(root->left,low,high);
		}
		root->left=trimBST(root->left,low,high);//接住新的左子结点
		root->right=trimBST(root->right,low,high);
		return root;
    }
};

迭代

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root&&(root->val < L || root->val > R)) {//!!!注意root为空则结束
            if (root->val < L) root = root->right; // 小于L往右走
            else  root = root->left; // 大于R往左走
        }
        TreeNode *cur = root;
        // 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;

        // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

将有序数组转换为二叉搜索树

求中间位置的时候使用int mid = l+(r-l)/2,而不是int mid = (l+r)/2,防止l,r都是很大的数值时操作越界。

class Solution {
public:
	TreeNode* traversal(vector<int>& nums,int l,int r){
		if(l>r){
			return NULL;
		}
		int mid=l+((r-l)/2);//若为偶数个，取中间左边那个
		TreeNode* root=new TreeNode(nums[mid]);
		root->left=traversal(nums,l,mid-1);
		root->right=traversal(nums,mid+1,r);
		return root;
	}
    TreeNode* sortedArrayToBST(vector<int>& nums) {
		TreeNode* root=traversal(nums,0,nums.size()-1);//左闭右闭
		return root;
    }
};

迭代法用三个队列分别存放结点、左区间下标、右区间下标

把二叉搜索树转换为累加树

递归法，遍历整个树，递归函数不用返回值

class Solution {
public:
	int pre=0;
	void traversal(TreeNode* cur){
		if(cur==NULL){
			return;
		}
		traversal(cur->right);
		cur->val+=pre;
		pre=cur->val;//下一个要加的值
		traversal(cur->left);
	}
    TreeNode* convertBST(TreeNode* root) {
		traversal(root);
		return root;
    }
};

迭代法，基本一样

class Solution {
public:
	int pre=0;
	void iteration(TreeNode* cur){
		stack<TreeNode*> s;
		while(cur!=NULL||!s.empty()){
			if(cur!=NULL){
				s.push(cur);
				cur=cur->right;
			}
			else{
				cur=s.top();
				s.pop();
				cur->val+=pre;
				pre=cur->val;
				cur=cur->left;
			}
		}
	}
    TreeNode* convertBST(TreeNode* root) {
		iteration(root);
		return root;
    }
};