@ 代码随想录算法训练营第4周（C语言）|Day22（二叉树）

@ 代码随想录算法训练营第4周（C语言）|Day22（二叉树）

Day22、二叉树（包含题目 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点 ）

235. 二叉搜索树的最近公共祖先

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

题目解答

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if(root==NULL){return root;}if(root->val>q->val&&root->val>p->val){struct TreeNode*left=lowestCommonAncestor(root->left,p,q);if(left!=NULL){return left;}}if(root->val<p->val&&root->val<q->val){struct TreeNode*right=lowestCommonAncestor(root->right,p,q);if(right!=NULL){return right;}}return root;
}

题目总结

所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。

701.二叉搜索树中的插入操作

题目描述

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

题目解答

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {if(root==NULL){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);}if(root->val<val){root->right=insertIntoBST(root->right,val);}return root;
}

题目总结

终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

450.删除二叉搜索树中的节点

题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

题目解答

struct TreeNode* deleteNode(struct TreeNode* root, int key){//五种终止情况if(root==NULL){return NULL;}if(root->val==key){if(root->left==NULL&&root->right==NULL){return NULL;}else if(root->left&&root->right==NULL){return root->left;}else if(root->right&&root->left==NULL){return root->right;}else{struct TreeNode*node=root->right;//找到右子树中最左端的节点街上左子树while(node->left){node=node->left;}node->left=root->left;return root->right;}}if(root->val>key){root->left=deleteNode(root->left,key);}else if(root->val<key){root->right=deleteNode(root->right,key);}return root;}

题目总结

五种情况。