513. 找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/

从题目和示例中,可以得知,题目要求的是:最后一层节点的第一个节点！

走一个层序遍历,记录每一层的第一个节点的值！

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        //层序遍历思想，用一个变量保存每一层最左边的值，当最后一层执行完循环之后，该变量就是最后一层最左边的值

        int leftVal = 0;//
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();//当层有多少个节点
            for(int i = 0;i<size;i++)
            {
                TreeNode* tmp = q.front();
                q.pop();
                if(i == 0) //当前节点是该层第一个节点(即当前曾最左节点)
                {
                    leftVal = tmp->val;
                }
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
        }
        return leftVal;
    }
};

501:二叉搜索树中的众数

class Solution {
private:
    int maxcount;//最大频率
    int count;//统计频率
    TreeNode* pre;//记录前一个节点的指针
    vector<int> result;//储存结果
    
    void searchBST(TreeNode* cur)
    {
        if(cur == NULL) return;
        searchBST(cur->left);
        
        if(pre == NULL)      //当前访问的节点是第一个节点,count为1
        {
            count = 1;
        }
        else if(pre->val == cur->val)//当前节点的值与前一个节点值相同,count++
        {
            count++;
        }
        else                         //与前一个节点值不同,重新将count置1
        {
            count = 1;
        }
        
        pre = cur;                   //更新上一个节点
        
        if(count == maxcount)        //如果和最大值相同，放进result中
        {
            result.push_back(cur->val);
        }
        if(count > maxcount)         //如果计数大于最大值频率
        {
            maxcount = count;        //更新最大频率
            result.clear();          //清空result中的之前元素
            result.push_back(cur->val);
        }
        
        searchBST(cur->right);      
        return;
    }
public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxcount = 0;
        TreeNode* pre = NULL;        //记录前一个节点
        result.clear();
        searchBST(root);
        return result;
    }
};

需要弄一个指针指向前一个节点，这样每次 cur（当前节点）才能和 pre（前一个节点）作比较。

而且初始化的时候 pre = NULL，这样当 pre 为 NULL 时候，我们就知道这是比较的第一个元素，然后再给 pre 赋值即 pre = cur;

频率 count 等于 maxCount，当然要把这个元素加入到结果集中

频率 count 大于 maxCount 的时候，不仅要更新 maxCount，而且要清空结果集（以下代码为 result 数组），因为结果集之前的元素都失效了

非递归:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> v;
        if(root == nullptr) return v;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        int count = 0;
        int maxCount =0;
        while(!st.empty() || cur!=nullptr)
        {
            //先将所有左节点入栈
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            //处理
            TreeNode* top = st.top();
            st.pop();
            //处理
            if(pre == nullptr)
                count = 1;
            else if(pre->val == top->val)
                count++;
            else
                count = 1;

            if(count > maxCount)
            {
                v.clear();
                v.push_back(top->val);
                maxCount = count;
            }
            else if(count == maxCount)
            {
                v.push_back(top->val);
            }
            pre = top;
            //去栈顶节点的右树访问
            cur = top->right;
        }
        return v;
    }
};