@代码随想录算法训练营第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; } 题目总结

五种情况。