代码随想录1016-Day16

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 + kroot->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;}
};