二叉树例题分享

文章目录

二叉树例题分享
- - [235. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/)
  - [701. 二叉搜索树中的插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)
  - [108. 将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)
  - [450. 删除二叉搜索树中的节点](https://leetcode.cn/problems/delete-node-in-a-bst/)

二叉树例题分享

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

题目

代码

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

题解

本题要求我们找到二叉搜索树中两个节点的最小公共祖先，因为是二叉搜索树，所以实现起来还是比较简单的，因为二叉搜索树的左子树数值一定小于根节点数值小于右子树数值。

多以我们遍历一遍二叉树就可以找到答案：

如果ans节点数值同时大于p，q数值，那么p，q一定在ans节点的左边，向左遍历；
如果ans节点数值同时小于p，q数值，那么p，q一定在ans节点的右边，向右遍历；
如果一大一小，那证明找到了最近公共祖先。

总体来说只要我们知道在什么情况下是最近公共祖先，我们就可以轻松实现本题要求。

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

题目

代码

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {struct TreeNode* ans = root;struct TreeNode* new = (struct TreeNode*)malloc(sizeof(struct TreeNode));new->left = NULL;new->right = NULL;new->val = val;if (root == NULL)return new;while (root) {if (root->val > val) {if (root->left != NULL)root = root->left;else {root->left = new;return ans;}} else {if (root->right != NULL)root = root->right;else {root->right = new;return ans;}}}return ans;
}

题解

本题可以使用两种方法去实现：

第一种：

迭代法

迭代法是我在没有看题解情况下完成的。

因为是二叉搜索树，所以我们遍历一次便可以实现。

我们在遍历二叉树的时候，如果本节点的数值大于val，则证明val应该插入到左子树中，反之插入右子树中，我们只需要继续判断本节点的左孩子节点（右孩子节点）是否为空，如果不为空则继续遍历，如果为空则证明该位置就为插入位置。

下面是代码：

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {if (root == NULL)return root;struct TreeNode* ans = root;struct TreeNode* new = (struct TreeNode*)malloc(sizeof(struct TreeNode));new->left = NULL;new->right = NULL;new->val = val;while (root) {if (root->val > val) {if (root->left != NULL)root = root->left;else {root->left = new;return ans;}} else {if (root->right != NULL)root = root->right;else {root->right = new;return ans;}}}return ans;
}

第二种：

递归法

终止递归是如果遇到了空节点，则证明该位置就应该是插入位置，直接返回新节点接可以了；
后面我们考虑一层递归的逻辑，我们判断val与root->val的大小关系，然后继续遍历左孩子节点或右孩子节点（之后会返回），并且用root->left或root->right接住返回值；
最后返回root就可以了。

最后的代码是这样的：

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {if (root == NULL) {struct TreeNode* new =(struct TreeNode*)malloc(sizeof(struct TreeNode));new->left = NULL;new->right = NULL;new->val = val;return new;}if (val > root->val)root->right = insertIntoBST(root->right, val);if (val < root->val)root->left = insertIntoBST(root->left, val);return root;
}

108. 将有序数组转换为二叉搜索树

题目

代码

struct TreeNode* Traval(int* nums, int left, int right) {if (left > right)return NULL;int mid = (left + right) / 2;struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = nums[mid];root->left = Traval(nums, left, mid - 1);root->right = Traval(nums, mid + 1, right);return root;
}struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {return Traval(nums, 0, numsSize - 1);
}

题解

本题要求我们将给定的升序数组转换成一棵平衡二叉搜索树。

我们的思路就是每次都将数组中的中间元素设置成根节点，然后将左边的设置为左子树，右边的设置为右子树，然后对左子树和右子树再进行相同的处理（运用递归）。

下面是代码：

struct TreeNode* Traval(int* nums, int left, int right) {if (left > right)return NULL;int mid = (left + right) / 2;struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = nums[mid];root->left = Traval(nums, left, mid - 1);root->right = Traval(nums, mid + 1, right);return root;
}struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {return Traval(nums, 0, numsSize - 1);
}

这里要说的是上面的终止条件（left>right），这里是因为我们传参是left和mid-1或者mid+1和right，如果left>right就证明节点为空，直接返回空节点就可以了。

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

题目

代码

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==NULL&&root->right!=NULL)return root->right;else if(root->left!=NULL&&root->right==NULL)return root->left;else if(root->left!=NULL&&root->right!=NULL){struct TreeNode* cur=root->right;while(cur->left!=NULL)cur=cur->left;cur->left=root->left;return root->right;}}if(root->val>key)root->left=deleteNode(root->left,key);if(root->val<key)root->right=deleteNode(root->right,key);return root;
}

题解

本题我们在删除的地方有五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

如果我们搞清楚了这五种情况，我们运用递归很容易就可以实现这道题。

已经到底啦！！