235. 二叉搜索树的最近公共祖先
题目链接/文章讲解：https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
视频讲解：https://www.bilibili.com/video/BV1Zt4y1F7ww
思路
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct 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 NULL;
}学习反思
在函数中使用了迭代的方式进行查找，先判断当前节点的值与目标节点的值的大小关系，然后根据不同的情况移动到左子树或右子树。如果当前节点的值位于目标节点的值之间，则说明当前节点就是最近公共祖先。时间复杂度为O(n)。
701.二叉搜索树中的插入操作
题目链接/文章讲解：https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html
视频讲解：https://www.bilibili.com/video/BV1Et4y1c78Y
思路
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->val = val;newNode->left = NULL;newNode->right = NULL;if (root == NULL) {return newNode;}struct TreeNode* current = root;struct TreeNode* parent = NULL;while (current != NULL) {parent = current; if (val < current->val) {current = current->left;} else {current = current->right; }}if (val < parent->val) {parent->left = newNode; } else {parent->right = newNode; }return root;
}学习反思
首先，创建一个新的节点，并将要插入的值赋给新节点的val属性。然后，判断树是否为空，如果为空，则直接返回新节点作为树的根节点。接下来，使用两个指针current和parent进行遍历和记录。初始化current为根节点，parent为NULL。在while循环中，遍历树，将parent指向当前节点，并根据要插入的值val和当前节点的值的大小关系，将current指向左子树或右子树。此时，current指向NULL，parent指向要插入位置的父节点。根据值的大小关系，将新节点插入到合适的位置，即parent的左子树或右子树。最后，返回树的根节点。时间复杂度为O(logn)到O(n)。
450.删除二叉搜索树中的节点
题目链接/文章讲解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
视频讲解：https://www.bilibili.com/video/BV1tP41177us
思路
struct TreeNode* deleteNode(struct TreeNode* root, int key) {if (root == NULL) {return NULL;}if (key < root->val) {root->left = deleteNode(root->left, key);} else if (key > root->val) {root->right = deleteNode(root->right, key);} else {if (root->left == NULL) {struct TreeNode* temp = root->right;free(root);return temp;} else if (root->right == NULL) {struct TreeNode* temp = root->left;free(root);return temp;} else {struct TreeNode* minNode = root->right;while (minNode->left != NULL) {minNode = minNode->left;}root->val = minNode->val;root->right = deleteNode(root->right, minNode->val);}}return root;
}学习反思
首先，判断根节点是否为空，如果为空，则直接返回null。接下来，根据要删除的值和当前节点的值的大小关系，递归地向左子树或右子树查找要删除的节点。
如果找到了要删除的节点，有以下几种情况：
- 如果要删除的节点没有左子树，直接返回右子树作为替代。
- 如果要删除的节点没有右子树，直接返回左子树作为替代。
- 如果要删除的节点有两个子节点，需要找到右子树中的最小节点，将其值替代当前节点的值，然后删除右子树中的最小节点。
最后，返回根节点。时间复杂度为O(logn)到O(n)。
总结
二叉树理解更深了，加油！！！
