体育器材网站模板,学it需要什么学历,电商类网站咋做,网站模块下载二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点
235. 二叉搜索树的最近公共祖先
方法一#xff1a;递归法#xff08;利用二叉搜索树性质#xff09;
class Solution {
public:TreeNode* lowestCommonAncestor(TreeN…二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点
235. 二叉搜索树的最近公共祖先
方法一递归法利用二叉搜索树性质
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootnullptr) return root;if(root-val p-val root-val q-val) //左{TreeNode* left lowestCommonAncestor(root-left,p,q);return left;}if(root-val p-val root-val q-val) //右{TreeNode* right lowestCommonAncestor(root-right,p,q);return right;}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 root;}
};701. 二叉搜索树中的插入操作
方法一递归找叶子节点
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(rootnullptr) {TreeNode* root new TreeNode(val);return root; //找到叶节点传给上一层递归}if(val root-val) root-left insertIntoBST(root-left,val); //向左遍历接收叶子节点的数值else root-right insertIntoBST(root-right,val);return root;}
};方法二递归找叶子节点但通过全局变量记录parent位置
class Solution {
public:TreeNode* parent; //插入位置的父节点void traversal(TreeNode* cur, int val){if(curnullptr) {if(parent-valval) parent-left new TreeNode(val);else parent-right new TreeNode(val);return;}parent cur; //进入上一层前提前保存叶子结点的父节点if(cur-valval) traversal(cur-left,val);else traversal(cur-right,val);return;}TreeNode* insertIntoBST(TreeNode* root, int val) {if(rootnullptr) { //根节点为null的特殊处理root new TreeNode(val);return root;}traversal(root, val);return root;}
};方法三迭代法
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if (root NULL) { //处理root为零特殊情况TreeNode* node new TreeNode(val);return node;}TreeNode* cur root;TreeNode* parent; // 这个很重要需要记录上一个节点否则无法赋值新节点while (cur ! NULL) {parent cur;if (cur-val val) cur cur-left;else cur cur-right;}//找到parent位置了接下来对parent的值和val对比确定放在左节点还是右节点TreeNode* node new TreeNode(val);if (val parent-val) parent-left node;// 此时是用parent节点的进行赋值else parent-right node;return root;}
};450. 删除二叉搜索树中的节点
有以下五种情况
第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
第五种情况有点难以理解看下面动画 动画中的二叉搜索树中删除元素7 那么删除节点元素7的左孩子就是5删除节点元素7的右子树的最左面节点是元素8。
将删除节点元素7的左孩子放到删除节点元素7的右子树的最左面节点元素8的左孩子上就是把5为根节点的子树移到了8的左孩子的位置。
要删除的节点元素7的右孩子元素9为新的根节点。.
这样就完成删除元素7的逻辑最好动手画一个图尝试删除一个节点试试。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root nullptr) return root; // 第一种情况没找到删除的节点遍历到空节点直接返回了if (root-val key) {// 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点if (root-left nullptr root-right nullptr) {///! 内存释放delete root;return nullptr;}// 第三种情况其左孩子为空右孩子不为空删除节点右孩子补位 返回右孩子为根节点else if (root-left nullptr) {auto retNode root-right;///! 内存释放delete root;return retNode;}// 第四种情况其右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点else if (root-right nullptr) {auto retNode root-left;///! 内存释放delete root;return retNode;}// 第五种情况左右孩子节点都不为空则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else {TreeNode* cur root-right; // 找右子树最左面的节点while(cur-left ! nullptr) {cur cur-left;}cur-left root-left; // 把要删除的节点root左子树放在cur的左孩子的位置TreeNode* tmp root; // 把root节点保存一下下面来删除root root-right; // 返回旧root的右孩子作为新rootdelete tmp; // 释放节点内存这里不写也可以但C最好手动释放一下吧return root;}}if (root-val key) root-left deleteNode(root-left, key);if (root-val key) root-right deleteNode(root-right, key);return root;}
};
