卓越亚马逊网站建设目的,凡科建站代理平台,腾讯营销平台,小程序appidday19 周日放假 今天依旧是二叉树环节
力扣题部分:
235. 二叉搜索树的最近公共祖先
题目链接:. - 力扣#xff08;LeetCode#xff09;
题面:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为#xff1a;“对于有根树 T …day19 周日放假 今天依旧是二叉树环节
力扣题部分:
235. 二叉搜索树的最近公共祖先
题目链接:. - 力扣LeetCode
题面:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
思路: 和day18的二叉树公共祖先不同的是这一次我们可以利用二叉搜索树的特点遍历一个路径就够了其他的倒没什么太大区别。
具体思路细节内容可以看day18的最后一题 236. 二叉树的最近公共祖先这里就不重复了。
传送门(day18):代码随想录算法训练营第十八天二叉树 六-CSDN博客
代码实现:
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(p - val q - val) swap(q, p);if(root - val p - val root - val q - val) return root;if(root - val p - val root - right) return lowestCommonAncestor(root - right, p, q);if(root - val q - val root - left) return lowestCommonAncestor(root - left, p, q);return nullptr;}
}; 701.二叉搜索树中的插入操作 题目链接:. - 力扣LeetCode 题面: 给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。 注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。 思路: 按照最简单的想法一条路径走到底最后创造一个叶子节点挂树上就好了可以不重构二叉树就不要重构二叉树了不然就很麻烦就像下一道题。 代码实现: class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(!root){TreeNode* newnode new TreeNode(val);return newnode;}if(root - val val) root - left insertIntoBST(root - left, val);if(root - val val) root - right insertIntoBST(root - right, val);return root;}
}; 450.删除二叉搜索树中的节点 题目链接:. - 力扣LeetCode 题面: 给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。 一般来说删除节点可分为两个步骤 首先找到需要删除的节点如果找到了删除它。 思路: 我们知道插入可以插入在叶子节点也可以不插入在叶子节点而删除就没得选择所有情况都要考虑那就得按需要删除的结点情况分类讨论了: 1.没找到。 解决办法遍历到空节点直接返回。 2.找到了在叶子节点上。 解决办法删除节点并返回空节点。 3.找到了左边有子树右边没有。 解决办法像链表一样要删除的节点的父节点指向要删除节点的左节点相当于绕过要删除的节点然后记得删除释放空间。 4.找到了右边右子树左边没有。 解决办法和第三条类似父节点指向删除节点的右节点。 5.找到了左右两边都有子树。 解决办法最难的部分。先讲操作将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。 我们知道二叉搜索树要保证中序遍历递增删除节点的左子树全部比右子树小该节点一删右节点像之前一样一补上去整个左子树就悬空了由于左子树都比右子树小所以只能把悬空的左子树根节点放在右节点最小的节点左侧这样就可以让中序遍历仍旧是递增的了。如果还有点懵可以尝试画个图自己手动删除节点理解一下 代码实现: class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root nullptr) return root; // 第一种情况if (root-val key) {// 第二种情况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;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;}
};
