前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 22，难熬的周三~
题目详情
[235] 二叉搜索树的最近公共祖先
题目描述
235 二叉搜索树的最近公共祖先
解题思路
前提：二叉搜索树，且p、q均存在于二叉树上
思路：后序遍历，判断是否同处于某结点的左右子树上，因二叉搜索树有序性，可以判断结点在左子树还是右子树。
重点：有可能p、q为左右子树上，也有可能p为q的祖先。
代码实现
C语言
普通二叉树的最近公共祖先解法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode *traversal(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q)
{// 判空if ((root == NULL) || (p == NULL) || (q == NULL)){return NULL;}// 判断该结点if ((root == p) || (root == q)){return root;}// 左子树struct TreeNode *leftNode = traversal(root->left, p, q);// 右子树struct TreeNode *rightNode = traversal(root->right, p, q);// 判断是否找到最近公共祖先if ((leftNode != NULL) &&(rightNode != NULL)){return root;}else if ((leftNode != NULL) &&(rightNode == NULL)){return leftNode;}else if ((leftNode == NULL) &&(rightNode != NULL)){return rightNode;}return NULL;
}struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {return traversal(root, p, q);
}
二叉搜索树的有序性解法
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode *traversal(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q)
{// 判空if ((root == NULL) || (p == NULL) || (q == NULL)){return NULL;}// p、q结点均在左子树上if ((root->val > p->val) && (root->val > q->val)){return traversal(root->left, p, q);}// p、q结点均在右子树上if ((root->val < p->val) && (root->val < q->val)){return traversal(root->right, p, q);}// p、q一左一右或者一左一根或者一根一右，此时root均为最近公共祖先return root;
}struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {return traversal(root, p, q);
}
[701] 二叉搜索树中的插入操作
题目描述
701 二叉搜索树中的插入操作
解题思路
前提：二叉搜索树
思路：由于二叉搜索树的有序性，插入的结点在对应叶子结点的左节点或右节点即可。
重点：二叉搜索树的有序性。
代码实现
C语言
递归
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/void traversal(struct TreeNode **root, int val)
{// 判空if (*root == NULL){*root = (struct TreeNode *)malloc(sizeof(struct TreeNode));(*root)->val = val;(*root)->left = NULL;(*root)->right = NULL;return ;}// 判断元素插入位置if ((*root)->val > val){traversal(&((*root)->left), val);}else if ((*root)->val < val){traversal(&((*root)->right), val);}return ;
}struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {traversal(&root, val);return root;
}
迭代
/*** 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 == NULL){root = (struct TreeNode *)malloc(sizeof(struct TreeNode));root->val = val;root->left = NULL;root->right = NULL;return root;}// 原树非空struct TreeNode *pre = NULL;struct TreeNode *cur = root;// 遍历至叶子结点位置while (cur){// 保存当前结点位置pre = cur;if (cur->val > val){cur = cur->left;}else if (cur->val < val){cur = cur->right;}}// 插入节点if (pre->val > val){pre->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));pre->left->val = val;pre->left->left = NULL;pre->left->right = NULL;}else if (pre->val < val){pre->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));pre->right->val = val;pre->right->left = NULL;pre->right->right = NULL;}return root;
}
[450] 删除二叉搜索树中的节点
题目描述
450 删除二叉搜索树中的节点
解题思路
前提：二叉搜索树
思路：由于二叉搜索树的有序性，删除的结点比较容易遍历到，主要是处理该删除结点的左右子树的处理。
重点：该删除结点的左右子树的处理，如果左右子树有一为NULL时，则该子树代替删除结点的位置；如果左右子树均不为NULL时，则需要将左子树挂在右子树的最左侧叶子结点的左结点上，或者将右子树挂在左子树最右侧叶子结点的右节点上。
代码实现
C语言
二叉搜索树递归
/*** 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 == NULL){return root;}// 判断是否为删除结点if (root->val == key){// 如果该结点的左右子树至少一空if (root->left == NULL){return root->right;}else if (root->right == NULL){return root->left;}else{// 寻找左侧子树的最右侧结点，放置该结点的右子树struct TreeNode *pre = root;struct TreeNode *cur = root->left;while (cur){pre = cur;cur = cur->right;}pre->right = root->right;root = root->left;return root;}}if (root->val > key){root->left = deleteNode(root->left, key);}if (root->val < key){root->right = deleteNode(root->right, key);}return root;
}
二叉搜索树迭代
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
struct TreeNode *deleteOneNode(struct TreeNode *root)
{// 判空if (root == NULL){return root;}// 删除结点if (root->left == NULL){return root->right;}if (root->right == NULL){return root->left;}// 该结点两子树均不为空时，寻找左子树的最右叶子结点的右子树位置，指向原结点的右子树struct TreeNode *cur = root->left;while (cur->right){cur = cur->right;}cur->right = root->right;return root->left;
}struct TreeNode* deleteNode(struct TreeNode* root, int key){// 判空if (root == NULL){return root;}// 查找删除结点struct TreeNode *pre = NULL;struct TreeNode *cur = root;while (cur){if (cur->val == key){break;}pre = cur;if (cur->val > key){cur = cur->left;}else if (cur->val < key){cur = cur->right;}}// 删除结点为根节点情况if (pre == NULL){return deleteOneNode(root);}// 判断删除结点为左子树，还是右子树if ((pre->left) && (pre->left->val == key)){pre->left = deleteOneNode(pre->left);}if ((pre->right) && (pre->right->val == key)){pre->right = deleteOneNode(pre->right);}return root;
}
普通二叉树删除方式：通过交换节点，然后删除叶子结点实现
/*** 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 == NULL){return root;}// 判断是否为删除结点if (root->val == key){// 如果该结点的左右子树至少一空，此时删除该结点if (root->left == NULL){return root->right;}else if (root->right == NULL){return root->left;}else{// 寻找该结点的左侧子树的最右侧结点，放置该结点的右子树,并交换两节点值struct TreeNode *pre = root;struct TreeNode *cur = root->left;while (cur){pre = cur;cur = cur->right;}int tmp = root->val;root->val = pre->val;pre->val = tmp;}}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;
}
今日收获
- 二叉搜索树的相关实现。
