235.二叉搜索树的最近公共祖先
链接:. - 力扣(LeetCode)
题目描述:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点5
和节点1
的最近公共祖先是节点3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点5
和节点4
的最近公共祖先是节点5 。
因为根据定义最近公共祖先节点可以为节点本身。示例 3:
输入:root = [1,2], p = 1, q = 2 输出:1提示:
- 树中节点数目在范围
[2, 105]
内。-109 <= Node.val <= 109
- 所有
Node.val
互不相同
。p != q
p
和q
均存在于给定的二叉树中。
思路:
根据搜索二叉树的性质可知道,当p小于某个节点的值,而q大于某个节点的值时,该节点就是这个二叉树的最近公共祖先
使用递归实现:
1.确定函数的参数和返回值,函数的参数应该为二叉树的根节点以及p和q,返回值应该为要找到的公共祖先
2.确定递归终止逻辑,如果节点为空,则返回空,如果当前结点的大于p且当前节点小于q,则该节点就是最近公共祖先,返回该节点
3.确定递归的单层逻辑,根据二叉搜索树的性质,可知遍历的方向,如果p和q都小于当前节点,则向左去遍历,否则向右去遍历
代码实现:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { if(root == NULL) return NULL; if(root->val > p->val && root->val < q->val) return root; if(root->val > p->val && root->val > q->val) { struct TreeNode *left = lowestCommonAncestor(root->left,p,q); return left; } if(root->val < p->val && root->val < q->val) { struct TreeNode *right = lowestCommonAncestor(root->right,p,q); return right; } return root; }
701.二叉搜索树的插入操作
链接:. - 力扣(LeetCode)
题目描述:
给定二叉搜索树(BST)的根节点
root
和要插入树中的值value
,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1:
输入:root = [4,2,7,1,3], val = 5 输出:[4,2,7,1,3,5] 解释:另一个满足题目要求可以通过的树是:示例 2:
输入:root = [40,20,60,10,30,50,70], val = 25 输出:[40,20,60,10,30,50,70,null,null,25]示例 3:
输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出:[4,2,7,1,3,5]提示:
- 树中的节点数将在
[0, 104]
的范围内。-108 <= Node.val <= 108
- 所有值
Node.val
是 独一无二 的。-108 <= val <= 108
- 保证
val
在原始BST中不存在。
思路:
因为题目要求的插入节点之后依旧是二叉搜索树的结构,因此我们可以想到将要插入的节点插入到叶子节点上,这样会更容易实现,不会改变原树的结构
递归实现:
1.确定函数的参数和返回值,函数的参数应该是二叉搜索树的根节点已经要插入的值,返回值应该为插入节点后的二叉树
2.确定递归终止条件,当我们找到适合插入的位置时,进行插入操作之后就返回该插入的节点,这个节点的信息就会传递给它的父节点
3.确定单层递归逻辑,判断要插入的值与当前节点的值的大小,如果大于当前节点的值,则遍历左子树,否则遍历右子树
代码实现:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* insertIntoBST(struct TreeNode* root, int val) { //符合条件的位置 if(!root) { //此时node为叶子节点,注意设置叶子节点在左右子树为空 struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node; } if(root->val > val) root->left = insertIntoBST(root->left, val); else root->right = insertIntoBST(root->right, val); return root; }
450.删除二叉搜索树中的节点
链接:. - 力扣(LeetCode)
题目描述:
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
- 首先找到需要删除的节点;
- 如果找到了,删除它。
示例 1:
输入:root = [5,3,6,2,4,null,7], key = 3 输出:[5,4,6,2,null,null,7] 解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点示例 3:
输入: root = [], key = 0 输出: []提示:
- 节点数的范围
[0, 104]
.-105 <= Node.val <= 105
- 节点值唯一
root
是合法的二叉搜索树-105 <= key <= 105
思路:
我们可以根据二叉搜索树的性质去查找二叉搜索树中要删除的值,不需要遍历整个二叉树,在搜索过程中,我们可以想到几种情况,分别是
1.没有找到我们要删除的值
2.找到了我们要删除的节点,该节点为叶子节点
3.找到了要删除的节点,该节点的左子树不为空,右子树为空
4.找到了要删除的节点,该节点左子树为空,右子树不为空
5.找到要删除的节点,该节点左右子树都不为空,需要对该节点的左右子树做出判断
递归实现思路:
1.确定函数的参数和返回值,函数的参数应该是我们要传入的二叉树已经要删除的值,返回值应该为删除节点后的二叉树
2.确定递归函数的终止条件:
当没有找到这个节点时,遇到空节点直接返回
当要删除的节点为叶子节点时,因为使用递归,返回NULL(其父节点接收该节点的位置变为空),释放该节点所占的内存空间
当要删除的节点有左子树没有右子树,进行删除操作,返回删除节点的左孩子,删除节点的父节点会接收删除节点的左孩子,进行内存释放
当要删除的节点没有左子树有右子树,进行删除操作,返回删除节点的右孩子,删除节点的父节点会接收删除节点的右孩子,进行内存释放
当删除的节点有左孩子也有右孩子,先找到其右孩子,再一直向左遍历,找到删除节点的右子树的最左叶子节点,将删除节点的左子树插入到最左叶子节点之后,这样不会改变二叉搜索树的结构
3.确定单层递归逻辑,根据要删除的值判断往左或右去查找
代码实现
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* deleteNode(struct TreeNode* root, int key){ //没有找到 if(!root) return root; //找到 if(root->val == key) { if(!root->left && !root->right) { //释放root,并让root的父节点指向空 free(root); return NULL; } else if(root->left && !root->right) { //记录root左子树,并返回该子树给删除节点的父节点 struct TreeNode *tem = root->left; free(root); return tem; } else if(!root->left && root->right) { //记录root右子树,并返回该子树给删除节点的父节点 struct TreeNode *tem = root->right; free(root); return tem; } else { //记录root右子树,并返回该子树给删除节点的父节点 struct TreeNode *cur = root->right; //找到右子树最左的叶子节点 while(cur->left) { cur = cur->left; } //要删除节点的左子树连接到右子树最左的叶子节点 cur->left = root->left; struct TreeNode *tem = root->right; free(root); return tem; } } //递归遍历 if(root->val > key) root->left = deleteNode(root->left,key); else root->right = deleteNode(root->right,key); return root; }