网站中在线咨询怎么做,大连建设公司网站,如何制作一个网站做淘宝券,康定网站建设公司文档讲解#xff1a; BST#xff0c;各种插入删除操作 235.二叉搜索树的最近公共祖先 思路#xff1a;昨天练习了二叉树的搜索#xff0c;今天这道题是二叉搜索树的搜索#xff0c;其具有有序这个特点#xff0c;其能决定我们每次搜索是进入该节点的左子树还是右子树 BST各种插入删除操作 235.二叉搜索树的最近公共祖先 思路昨天练习了二叉树的搜索今天这道题是二叉搜索树的搜索其具有有序这个特点其能决定我们每次搜索是进入该节点的左子树还是右子树而且其具有一个特点一旦要搜索的节点p和节点q不存在同一个子树中那么此时的root一定是他们两个的最近公共祖先 时间复杂度O(n) 空间复杂度O(n) class Solution {
public:TreeNode* traversal(TreeNode* root,TreeNode* p,TreeNode* q){if(rootnullptr)return root;//只要p和q分别存在于该root的两棵子树中的时候就可以返回了if(root-valp-valroot-valq-val){TreeNode* lefttreetraversal(root-left,p,q);//出栈回到最上面一层if(lefttree!nullptr){return lefttree;}}if(root-valp-valroot-valq-val){TreeNode* righttreetraversal(root-right,p,q);if(righttree!nullptr){return righttree;}}return root;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};701.二叉搜索树中的插入操作 思路其实这道题看起来复杂做起来容易就是无论如何我们都将要插入的节点插入到最后一个位置每次只需要比较其比根节点大还是小放在左子树还是右子树 时间复杂度O(n) 空间复杂度O(n) class Solution {
public:TreeNode* traversal(TreeNode* root,int val){if(rootnullptr){TreeNode* nodenew TreeNode(val);return node;}if(valroot-val){root-lefttraversal(root-left,val);}if(valroot-val){root-righttraversal(root-right,val);}return root;}TreeNode* insertIntoBST(TreeNode* root, int val) {return traversal(root,val);}
};450.删除二叉搜索树中的节点 思路这里的调整树的结构还得学习一下 时间复杂度O(n) 空间复杂度O(n) class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(rootnullptr)return root;if(root-valkey){if(root-leftnullptrroot-rightnullptr){delete root;return nullptr;}if(root-leftnullptrroot-right){TreeNode* temproot;rootroot-right;delete temp;return root;}else if(root-leftroot-rightnullptr){TreeNode* temproot;rootroot-left;delete temp;return root;}else{TreeNode* curroot-right;while(cur-left!nullptr){curcur-left;}cur-leftroot-left;TreeNode* temproot;rootroot-right;delete temp;tempnullptr;}}if(root-valkey)root-leftdeleteNode(root-left,key);if(root-valkey)root-rightdeleteNode(root-right,key);return root;}
};
