二叉树例题分享

二叉树例题分享

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

题解

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

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

• 如果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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

题解

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

第一种：

​ 迭代法

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

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

我们在遍历二叉树的时候，如果本节点的数值大于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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

第二种：

​ 递归法

• 终止递归是如果遇到了空节点，则证明该位置就应该是插入位置，直接返回新节点接可以了；
• 后面我们考虑一层递归的逻辑，我们判断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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

题解

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

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

下面是代码：

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里要说的是上面的终止条件（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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题解

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

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

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

已经到底啦！！