{"id":7119,"date":"2020-07-18T22:14:52","date_gmt":"2020-07-19T05:14:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7119"},"modified":"2020-07-18T23:45:12","modified_gmt":"2020-07-19T06:45:12","slug":"leetcode-1519-number-of-nodes-in-the-sub-tree-with-the-same-label","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1519-number-of-nodes-in-the-sub-tree-with-the-same-label\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label"},"content":{"rendered":"\n

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n<\/code> nodes numbered from 0<\/code> to n - 1<\/code> and exactly n - 1<\/code> edges<\/code>. The root<\/strong> of the tree is the node 0<\/code>, and each node of the tree has a label<\/strong> which is a lower-case character given in the string labels<\/code> (i.e. The node with the number i<\/code> has the label labels[i]<\/code>).<\/p>\n\n\n\n

The edges<\/code> array is given on the form edges[i] = [ai<\/sub>, bi<\/sub>]<\/code>, which means there is an edge between nodes ai<\/sub><\/code> and bi<\/sub><\/code> in the tree.<\/p>\n\n\n\n

Return an array of size n<\/code><\/em> where ans[i]<\/code> is the number of nodes in the subtree of the ith<\/sup><\/code> node which have the same label as node i<\/code>.<\/p>\n\n\n\n

A subtree of a tree T<\/code> is the tree consisting of a node in T<\/code> and all of its descendant nodes.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = \"abaedcd\"\nOutput:<\/strong> [2,1,1,1,1,1,1]\nExplanation:<\/strong> Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.\nNode 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 4, edges = [[0,1],[1,2],[0,3]], labels = \"bbbb\"\nOutput:<\/strong> [4,2,1,1]\nExplanation:<\/strong> The sub-tree of node 2 contains only node 2, so the answer is 1.\nThe sub-tree of node 3 contains only node 3, so the answer is 1.\nThe sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.\nThe sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = \"aabab\"\nOutput:<\/strong> [3,2,1,1,1]\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = \"cbabaa\"\nOutput:<\/strong> [1,2,1,1,2,1]\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = \"aaabaaa\"\nOutput:<\/strong> [6,5,4,1,3,2,1]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= n <= 10^5<\/code><\/li>
  • edges.length == n - 1<\/code><\/li>
  • edges[i].length == 2<\/code><\/li>
  • 0 <= ai<\/sub>, bi<\/sub> < n<\/code><\/li>
  • ai<\/sub> != bi<\/sub><\/code><\/li>
  • labels.length == n<\/code><\/li>
  • labels<\/code> is consisting of only of lower-case English letters.<\/li><\/ul>\n\n\n\n
    Solution: Post order traversal + hashtable<\/strong><\/h2>\n\n\n\n
    For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current –  before.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector countSubTrees(int n, vector>& edges, \n                            string_view labels) {\n    vector> g(n);    \n    for (const auto& e : edges) {\n      g[e[0]].push_back(e[1]);\n      g[e[1]].push_back(e[0]);\n    }\n    vector seen(n);\n    vector count(26);\n    vector ans(n);\n    function postOrder = [&](int i) {\n      if (seen[i]++) return;\n      int before = count[labels[i] - 'a'];\n      for (int j : g[i]) postOrder(j);        \n      ans[i] = ++count[labels[i] - 'a'] - before;\n    };\n    postOrder(0);\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\n  private List> g;\n  private String labels;\n  private int[] ans;\n  private int[] seen;\n  private int[] count;\n  \n  public int[] countSubTrees(int n, int[][] edges, String labels) {\n    this.g = new ArrayList>(n);\n    this.labels = labels; \n    for (int i = 0; i < n; ++i)\n      this.g.add(new ArrayList());\n    for (int[] e : edges) {\n      this.g.get(e[0]).add(e[1]);\n      this.g.get(e[1]).add(e[0]);\n    }\n    this.ans = new int[n];\n    this.seen = new int[n];\n    this.count = new int[26];\n    this.postOrder(0);\n    return ans;\n  }\n  \n  private void postOrder(int i) {\n    if (this.seen[i]++ > 0) return;\n    int before = this.count[this.labels.charAt(i) - 'a'];\n    for (int j : this.g.get(i)) this.postOrder(j);\n    this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;    \n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def countSubTrees(self, n: int, edges: List[List[int]], \n                    labels: str) -> List[int]:\n    g = [[] for _ in range(n)]\n    for u, v in edges:\n      g[u].append(v)\n      g[v].append(u)\n    seen = [False] * n\n    count = [0] * 26\n    ans = [0] * n\n    def postOrder(i):\n      if seen[i]: return\n      seen[i] = True\n      before = count[ord(labels[i]) - ord('a')]\n      for j in g[i]: postOrder(j)\n      count[ord(labels[i]) - ord('a')] += 1\n      ans[i] = count[ord(labels[i]) - ord('a')] - before\n    postOrder(0)\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n – 1 and exactly n – 1 edges. The root of the tree is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[82,56,17,28],"class_list":["post-7119","post","type-post","status-publish","format-standard","hentry","category-tree","tag-hashtable","tag-postorder","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7119"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7119\/revisions"}],"predecessor-version":[{"id":7121,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7119\/revisions\/7121"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}