当前位置：首页 > article >正文

代码随想录1016-Day16

article 2024/11/24 8:22:37

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

文章链接:代码随想录
题目链接：题目

思路：用中序遍历遍历一遍 BST 的所有节点得到有序结果，然后在遍历过程中计算最小差值即可
需要用一个pre节点记录一下cur节点的前一个节点：在递归中记录前一个节点的指针

    
/**
 * 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 res = INT_MAX;
    TreeNode * prev = nullptr;
    int getMinimumDifference(TreeNode* root) {
        traverse(root);
        return res;
    }
    void traverse(TreeNode* root)
    {
        if(!root) return;
        traverse(root->left);
        if(prev)
        {
            res = min(res, abs(root->val - prev->val));
        }
        prev = root;
        traverse(root->right);
    }
};

501.二叉搜索树中的众数

文章链接:代码随想录
题目链接：题目

思路：
这道题需要用到「遍历」的思维。

BST 的中序遍历有序，在中序遍历的位置做一些判断逻辑和操作有序数组差不多，很容易找出众数。
注意：
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了

class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    vector<int> result;
    void searchBST(TreeNode* cur) {
        if (cur == NULL) return ;

        searchBST(cur->left);       // 左
                                    // 中
        if (pre == NULL) { // 第一个节点
            count = 1;
        } else if (pre->val == cur->val) { // 与前一个节点数值相同
            count++;
        } else { // 与前一个节点数值不同
            count = 1;
        }
        pre = cur; // 更新上一个节点

        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

105.从中序与前序遍历序列构造二叉树

文章链接:代码随想录
题目链接：题目

思路：
构造二叉树，第一件事一定是找根节点，然后想办法构造左右子树。
在这里插入图片描述

二叉树的前序和中序遍历结果的特点如下：

在这里插入图片描述

前序遍历结果第一个就是根节点的值，然后再根据中序遍历结果确定左右子树的节点。

/**
 * 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:
    unordered_map<int, int> hash;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++)
        {
            hash[inorder[i]] = i;
        }
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
    TreeNode* buildTree(vector<int>&preorder,int pl, int pr, vector<int>& inorder, int il, int ir)
    {
        if(pl > pr) return nullptr;
        auto val = preorder[pl];
        //根据前序遍历的值 从哈希表中找到对应中序遍历的下标
        int k = hash[val];
        int lLength = k - il;
        TreeNode* root = new TreeNode(val);
        //pl + lLength有点没懂 
        //k - 1 - il
        // pl + 1 + k - 1 - il =>pl + k - il => pl + k
        root->left = buildTree(preorder, pl + 1, pl + lLength, inorder, il, k - 1);
        root->right = buildTree(preorder, pl + lLength + 1, pr, inorder, k + 1, ir);
        return root;
    }
};