仿淘宝商城网站开源系统,外贸网站打开速度,网站开发就是ssh吗,服装网站建设美丽题目#xff1a;二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为#xff1a;“对于有根树 T 的两个结点 p、q#xff0c;最近公共祖先表示为一个结点 x#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
题解 本题是二叉搜索树二叉搜索树是有序的那得好好利用一下这个特点。因为是有序树所有 如果 中间节点是 q 和 p 的公共祖先那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 p 中节点 q 或者 中节点 q 中节点 p。 从根节点搜索第一次遇到 cur节点是数值在[q, p]区间中此时可以说明 q 和 p 一定分别存在于 节点 的左子树和右子树中。所以当我们从上向下去递归遍历第一次遇到 cur节点是数值在[q, p]区间中那么cur就是 q和p的最近公共祖先。 确定递归函数返回值以及参数参数就是当前节点以及两个结点 p、q。返回值是要返回最近公共祖先所以是TreeNode * 。 确定终止条件 确定单层递归的逻辑那么如果 cur-val 大于 p-val同时 cur-val 大于q-val那么就应该向左遍历说明目标区间在左子树上。 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* leftlowestCommonAncestor(root-left,p,q);if(left!nullptr){return left;}}if(root-val p-val root-val q-val){TreeNode* rightlowestCommonAncestor(root-right,p,q);if(right!nullptr){return right;}}return root;}
};题目二叉搜索树中的插入操作
给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
题解 只要遍历二叉搜索树找到空节点 插入元素就可以了那么这道题其实就简单了。 确定递归函数参数以及返回值参数就是根节点指针以及要插入元素返回值的话可以利用返回值完成新加入的节点与其父节点的赋值操作。递归函数的返回类型为节点类型TreeNode * 。 确定终止条件终止条件就是找到遍历的节点为null的时候就是要插入节点的位置了并把插入的节点返回。 确定单层递归的逻辑搜索树是有方向了可以根据插入元素的数值决定递归方向。到这里大家应该能感受到如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了下一层将加入节点返回本层用root-left或者root-right将其接住。 class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root nullptr){TreeNode* temp_node new TreeNode(val);return temp_node;}if(root-val val){root-left insertIntoBST(root-left,val);}if(root-val val){root-right insertIntoBST(root-right,val);}return root;}
};题目删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。一般来说删除节点可分为两个步骤首先找到需要删除的节点然后删除它。
题解 确定递归函数参数以及返回值 确定终止条件 确定单层递归的逻辑:这里就把二叉搜索树中删除节点遇到的情况都搞清楚。 第一种情况没找到删除的节点遍历到空节点直接返回了 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点 第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点 第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点 第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。 class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(rootnullptr){return root;}if(root-val key){if(root-left nullptr root-right nullptr){delete root;return nullptr;}else if(root-left nullptr){auto temproot-right;delete root;return temp;}else if(root-right nullptr){auto temproot-left;delete root;return temp;}else{TreeNode* curroot-right;while(cur-left ! nullptr){curcur-left;}cur-leftroot-left;TreeNode* temp root;root root-right; // 返回旧root的右孩子作为新rootdelete temp;return root;}}if(root-val key) root-leftdeleteNode(root-left,key);if(root-val key) root-rightdeleteNode(root-right,key);return root;}
};因为二叉搜索树添加节点只需要在叶子上添加就可以的不涉及到结构的调整而删除节点操作涉及到结构的调整。这里最关键的逻辑就是第五种情况删除一个左右孩子都不为空的节点这种情况一定要想清楚。
