91嫩草久久久天美传媒,俺来了俺去了不卡,1000部成人无码视频,水蜜桃无码观看,美女操逼逼网站,色鬼久久综合,日本黄色视屏网站,特黄AAAAAAAA免费看直播

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 統(tǒng)計(jì)同值子樹，我們先來(lái)看題面：

https://leetcode-cn.com/problems/count-univalue-subtrees/

Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.

給定一個(gè)二叉樹，統(tǒng)計(jì)該二叉樹數(shù)值相同的子樹個(gè)數(shù)。

同值子樹是指該子樹的所有節(jié)點(diǎn)都擁有相同的數(shù)值。

示例

Input: root = [5,1,5,5,5,null,5]

              5
             / \
            1   5
           / \ \
          5   5   5

Output: 4

解題

節(jié)點(diǎn)node若是同值子樹點(diǎn)，則其左右子樹首先都是同值子樹點(diǎn)，并且左右孩子的val與node的val相同。介于此，遍歷node的時(shí)候，對(duì)左右子樹dfs返回一個(gè)bool值，若都為真，再將三者的val進(jìn)行對(duì)比，否則直接返回false。

class Solution {
public:
    int countUnivalSubtrees(TreeNode* root) {
        int sum=0;
        helper(root,sum);
        return sum;
    }
    bool helper(TreeNode* node,int& sum){
        if(node==0){
            return true;
        }
        bool le=helper(node->left,sum),ri=helper(node->right,sum);
        if(le and ri){
            if(node->left and node->left->val!=node->val){
                return false;
            }
            if(node->right and node->right->val!=node->val){
                return false;
            }
            ++sum;
            return true;
        }
        return false;
    }
};