[算法训练营] 二叉树专题(三)-阿里云开发者社区

前言

本篇为二叉树专题的刷题题单，总共7道题，每道题都有对应的链接。

边听歌边刷题吧~

Yesterday

236. 二叉树的最近公共祖先

链接：236. 二叉树的最近公共祖先

解题思路

@代码随想录

卡哥讲的很清楚

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==q || root==p || root==NULL)return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left!=NULL && right!=NULL)return root;
        if(left==NULL&&right!=NULL)return right;
        else if(left!=NULL&&right==NULL)return left;
        else return NULL;
    }
};

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

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

解题思路

更好的题解参考代码随想录，这里只记录我的理解
方法一
遍历整颗树，找它的最近公共祖先，就和236题一样
方法二
利用二叉搜索树的性质：从根开始，从上往下开始，找两个节点的公共根节点，只要这个节点的值在两个节点的值之间，这个节点就是这两个节点的最近公共根节点
所以我们只需要找到这个节点就可以了，从上往下，如果这个值大于那两个节点的值就往左子树走
否则往右子树走
直到节点的值在两个节点值的中间即可返回节点

AC代码

方法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q || root==NULL)return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left!=NULL && right!=NULL)return root;
        if(left==NULL)return right;
        return left;
    }
};

方法二

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//方法二
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)return NULL;
        if(root->val > q->val && root->val > p->val){
            TreeNode* left= lowestCommonAncestor(root->left,p,q);
            if(left!=NULL)return left;
        }
        if(root->val < p->val && root->val < q->val){
            TreeNode* right= lowestCommonAncestor(root->right,p,q);
            if(right!=NULL)return right;
        }
        return root;
    }
};

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

链接：

解题思路

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
推荐题解@代码随想录

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode*node = new TreeNode(val);
            return node;
        }
        if(root->val > val)root->left=insertIntoBST(root->left,val);
        if(root->val < val)root->right=insertIntoBST(root->right,val);
        return root;
    }
};

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

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

解题思路

利用二叉搜索树的性质→该节点左边的值比该节点小，右边的值比该节点大
其他的情况都比较简单，在代码中都注释了，这里只讲一下找到这个节点的时候，它的左右节点都不为空时
在找到这个要求删除的节点的时候，可以把这个节点的左子树接到该节点右子树的最左边的节点，然后让该节点变为该节点的右节点即可
如下图所示

AC代码

/**
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr)return nullptr;
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr){
                delete root;
                return nullptr;
            }else if(root->left==nullptr){
                auto resnode=root->right;
                delete root;
                return resnode;
            }else if(root->right==nullptr){
                auto resnode=root->left;
                delete root;
                return resnode;
            }else{
                TreeNode* cur=root->right;
                while(cur->left!=nullptr){
                    cur=cur->left;
                }
                cur->left=root->left;
                root=root->right;
                return root;
            }
        }
        if(root->val>key)root->left=deleteNode(root->left,key);
        if(root->val<key)root->right=deleteNode(root->right,key);
        return root;
    }
};

669. 修剪二叉搜索树

链接：669. 修剪二叉搜索树

解题思路

题目要求修改二叉搜索树，使得所有节点的值在[low, high]中
那么就需要遍历二叉树，当节点的值小于low时，这个节点的左子树就可以不用管，可以连同这个节点一起删除，只需要将右子树保留即可
当节点的值大于high时，这个节点的右子树就可以不用管，可以连同这个节点一起删除，只需要将左子树保留即可

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr)return root;
        if(root->val < low){
            TreeNode* right=trimBST(root->right,low,high);
            return right;
        }
        if(root->val > high){
            TreeNode* left=trimBST(root->left,low,high);
            return left;
        }
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
        return root;
    }
};

538. 把二叉搜索树转换为累加树

把二叉搜索树转换为累加树

解题思路

题目要求的是让每个节点的值等于该树中所有大于等于该节点的值的和
而且题目提供的是一棵二叉搜索树，它的中序遍历是单调递增的
所以可以反向中序遍历，使用一个变量pre来保存这个节点之前的节点和
后面的每个节点只需要加上pre，然后更新pre的值为pre加上当前节点的值即可

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pre=0;
    void traval(TreeNode* cur)
    {
        if(cur==nullptr)return;
        traval(cur->right);
        cur->val += pre;
        pre=cur->val;
        traval(cur->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        traval(root);
        return root;
    }
};

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

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

解题思路

当我们面对解决问题时，首先要明确问题的具体要求。在这道题中，我们需要将一个有序数组转换为一棵二叉搜索树。这里的关键是理解二叉搜索树的特性：对于任意一个节点，它的左子树中的所有节点都小于它，而右子树中的所有节点都大于它。

接下来，我们可以使用递归来解决这个问题。递归是一种常用的解决复杂问题的方法，它将问题分解为更小的子问题来解决。

首先，我们需要确定递归的终止条件。在这道题中，当左边界大于右边界时，说明已经没有元素可用了，此时我们应该返回空节点。

接着，我们需要在递归的每一层中选择合适的节点值，并创建节点。我们可以选择数组中间的元素作为当前节点的值，然后创建一个新的节点。

接下来，我们需要递归地构建当前节点的左子树和右子树。左子树的范围是从左边界到中间元素的前一个位置，右子树的范围是从中间元素的后一个位置到右边界。

最后，我们返回当前节点，完成一次递归。

通过这样的递归过程，我们可以逐步构建出一棵符合要求的二叉搜索树。

在编写代码时，我们还需要注意一些细节。当计算中间位置时，为了避免整数溢出的问题，我们可以使用 int mid = left + ((right - left) / 2); 的方式来计算中间位置。

另外，在调用 traversal 函数时，我们传入的左边界 left 是 0，右边界 right 是 nums.size() - 1，因为题目中给出的数组是有序的且没有重复元素，所以这样的范围划分是合理的。

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* traval(vector<int>& nums,int left,int right){
        if(left>right)return nullptr;
        int mid=left+(right-left)/2;
        TreeNode* node=new TreeNode(nums[mid]);
        node->left=traval(nums,left,mid-1);
        node->right=traval(nums,mid+1,right);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traval(nums,0,nums.size()-1);
    }
};

[算法训练营] 二叉树专题(三)

前言

236. 二叉树的最近公共祖先

解题思路

AC代码

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

解题思路

AC代码

方法一

方法二

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

解题思路

AC代码

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

解题思路

AC代码

669. 修剪二叉搜索树

解题思路

AC代码

538. 把二叉搜索树转换为累加树

解题思路

AC代码

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

解题思路

AC代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景