每日刷题 Day21

题一：左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/   \
9 20
   /  \
15 7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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 l=0;
    int sumOfLeftLeaves(TreeNode* root) {
        if(root==nullptr)
            return 0;
        if(root->left!=NULL&&root->left->left==NULL&&root->left->right==NULL)
            l+=root->left->val;
        sumOfLeftLeaves(root->left);
        sumOfLeftLeaves(root->right);
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题二：二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：
输入：root = [1,null,2,2]
输出：[2]

示例 2：
输入：root = [0]
输出：[0]

提示：
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

/**
 * 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:
    //用来统计树中数据出现的频率
    void find(TreeNode* root,unordered_map<int,int> &m){
        if(root==NULL)
            return;
        m[root->val]++;
        find(root->left,m);
        find(root->right,m);
    }
    //用来对哈希表进行排序
    bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        unordered_map<int,int> m;
        vector<int> str;
        find(root,m);
        vector<pair<int, int>> vec(m.begin(), m.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        str.push_back(vec[0].first);    //表中第一个元素即是出现次数最多的元素
        for(int i=1;i<vec.size();i++){  //查找是否有出现频率相同的元素
            if(vec[0].second==vec[i].second){
                str.push_back(vec[i].first);
            }    
        }
        return str;
    }
};
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
28
29
30
31
32
33
34
35
36
37
38
39
40

题三：二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

示例 1：
输入：root = [4,2,6,1,3]
输出：1

示例 2：
输入：root = [1,0,48,null,null,12,49]
输出：1

提示：
树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst

/**
 * 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:
    //利用前序遍历，遍历树，将树结点的所有值存在一个数组中
    void getNumber(TreeNode* root,vector<int> &str){
        if(root==NULL)
            return;
        str.push_back(root->val);
        getNumber(root->left,str);
        getNumber(root->right,str);
    }
    int getMinimumDifference(TreeNode* root) {
        vector<int> str;
        getNumber(root,str);
        int min=abs(str[1]-str[0]);
        int temp=0;
        //寻找最小绝对差
        for(int j=0;j<str.size();j++){
            for(int i=j+1;i<str.size();i++){
                temp=abs(str[i]-str[j]);
                if(min>temp)
                    min=temp;
            }
        }
        
        return min;
    }
};
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
28
29
30
31
32
33
34
35
36
37
38