250. 统计同值子树（二叉树）

给定一个二叉树，统计该二叉树数值相同的子树个数。

同值子树是指该子树的所有节点都拥有相同的数值。

---

示例：

输入: root = [5,1,5,5,5,null,5]

              5
             / \
            1   5
           / \   \
          5   5   5

输出: 4
1
2
3
4
5
6
7
8
9
10
11

---

【思路】：
遍历每个节点，看每个节点形成的树是否都是同值的。如果是，就res++即可。

代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var istongzhi = function(node, val){
    if(node == null)    return true;
    if(node.val == val){
        return istongzhi(node.left, val) && istongzhi(node.right, val);
    }else{
        return false;
    }
}

var order = function(node, res){
    if(node){
        if(istongzhi(node, node.val)){
            res.cnt++;
        }
        order(node.left, res);
        order(node.right, res);
    }
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countUnivalSubtrees = function(root) {
    var res = {cnt:0};
    order(root, res);
    return res.cnt;
};
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