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

前言

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

边听歌边刷题吧~

🎸Phantom

654. 最大二叉树

链接：最大二叉树

解题思路

每次以当前数组中最大的那个值为分割点
将数组分为左右子树构建左子树和右子树

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* constructMaximumBinaryTree(vector<int>& nums) { 
    if(nums.size()==0)return nullptr; 
    int maxnum=0; 
    for(int i=0;i<nums.size();++i) { 
        if(nums[i]>nums[maxnum])maxnum=i; 
    } 
    int rootVal=nums[maxnum]; 
    TreeNode* root=new TreeNode(rootVal); 
    if(nums.size()==1)return root; 
    vector<int> nleftTree(nums.begin(),nums.begin()+maxnum); 
    vector<int> nrightTree(nums.begin()+maxnum+1,nums.end()); 
    root->left=constructMaximumBinaryTree(nleftTree); 
    root->right=constructMaximumBinaryTree(nrightTree); 
    return root;
    } 
};

617. 合并二叉树

链接：617. 合并二叉树

解题思路

由题可得，两颗树都有的节点就相加
一个树没有就将另一棵树的那一节直接加到新的树的节点上

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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr)return root2;
        if(root2==nullptr)return root1;
        TreeNode* root = new TreeNode(0);
        root->val = root1->val + root2->val;
        root->left = mergeTrees(root1->left,root2->left);
        root->right = mergeTrees(root1->right,root2->right);
        return root;
    }
};

700. 二叉搜索树中的搜索

链接：700. 二叉搜索树中的搜索

解题思路

题目要求返回BST 中找到节点值等于 val 的节点的子树
其实就是找到那个节点
已知这颗树是二叉搜索树，那么就可以利用左边比根节点大，右边比根节点小的性质
其次还要使用一个变量来记录搜索的返回值
终止条件是节点为NULL时，说明到了叶子节点还没有找到
或者是节点的值相等说明找到了

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* searchBST(TreeNode* root, int val) {
        //终止条件
        if (root == NULL || root->val == val) return root;
        TreeNode* result=nullptr;
        if(root->val > val)result = searchBST(root->left,val);
        if(root->val < val)result = searchBST(root->right,val);
        return result;
    }
};

98. 验证二叉搜索树

链接：98. 验证二叉搜索树

解题思路

记得二叉树的中序遍历是递增的不含重复元素的即可

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* pre=nullptr;
    bool isValidBST(TreeNode* root) {
        if(root==nullptr)return true;//如果二叉搜索树为空，它也是二叉搜索树
        bool l=isValidBST(root->left);
        //中序遍历时，二叉搜索树是顺序递增的(不包含重复元素)
        if(pre!=nullptr&&pre->val >= root->val)return false;
        pre=root;//记录前一个节点的值
        bool r=isValidBST(root->right);
        return l&&r;
    }
};

迭代法

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL; // 记录前一个节点
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;                // 左
            } else {
                cur = st.top();                 // 中
                st.pop();
                if (pre != NULL && cur->val <= pre->val)
                return false;
                pre = cur; //保存前一个访问的结点
                cur = cur->right;               // 右
            }
        }
        return true;
    }
};

530. 二叉搜索树的最小绝对差

链接：530. 二叉搜索树的最小绝对差

解题思路

求最小差值、绝对值
已知二叉搜索树的中序遍历是递增且不含重复元素的
故可使用中序遍历，用一个变量记录前一个节点，如果前一个节点不为空则对比最小值
也可以将这个二叉搜索树的中序遍历为一个数组，然后遍历数组。
还可以使用栈来将树按照中序遍历的顺序读取然后比较

AC代码

递归法

class Solution {
public:
    TreeNode*pre = nullptr;
    int res=INT_MAX;
    void getMinGap(TreeNode* root){
        if(root==nullptr)return;
        getMinGap(root->left);
        if(pre!=nullptr){
            res=min(res,root->val-pre->val);
        }
        pre=root;
        getMinGap(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        getMinGap(root);
        return res;
    }
};

数组法

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};

迭代法

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int result = INT_MAX;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();
                if (pre != NULL) {              // 中
                    result = min(result, cur->val - pre->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

501. 二叉搜索树中的众数

链接：501. 二叉搜索树中的众数

解题思路

根据二叉搜索树的性质可以使用中序遍历
使用计数器记录相同的数字
一个记录前一个节点的变量，需要判断和前一个是否相同
如果节点不同就需要判断数量大小

数量相同就存入数组
数量更多就把数组清空将新的节点的数字存入数组，然后重新计数

如果碰到节点数字和前一个不同就将计数重置，更新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:
    TreeNode* pre=nullptr;
    vector<int> v;
    int maxcount=0;
    int count=0;
    void travel(TreeNode* root){
        if(root==nullptr)return;
        travel(root->left);
        if(pre->val == root->val)count++;
        else if(pre->val != root->val){
            pre = root;
            count=1;
        }
        if(count==maxcount){
            v.push_back(root->val);
        }
        if(count>maxcount)
        {
            maxcount=count;
            v.clear();
            v.push_back(root->val);
        }
        travel(root->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        pre = root;
        travel(root);
        return v;
    }
};

【算法训练营】二叉树专题(二)

前言

654. 最大二叉树

解题思路

AC代码

617. 合并二叉树

解题思路

AC代码

700. 二叉搜索树中的搜索

解题思路

AC代码

98. 验证二叉搜索树

解题思路

AC代码

递归法

迭代法

530. 二叉搜索树的最小绝对差

解题思路

AC代码

递归法

数组法

迭代法

501. 二叉搜索树中的众数

解题思路

AC代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景