{"id":7154,"date":"2020-07-25T23:32:13","date_gmt":"2020-07-26T06:32:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7154"},"modified":"2020-07-26T10:18:20","modified_gmt":"2020-07-26T17:18:20","slug":"leetcode-1530-number-of-good-leaf-nodes-pairs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1530-number-of-good-leaf-nodes-pairs\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1530. Number of Good Leaf Nodes Pairs"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1530. Number of Good Leaf Nodes Pairs - \u5237\u9898\u627e\u5de5\u4f5c EP346\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/g8AVmVhNTkM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given the&nbsp;<code>root<\/code>&nbsp;of a binary tree and an integer&nbsp;<code>distance<\/code>. A pair of two different&nbsp;<strong>leaf<\/strong>&nbsp;nodes of a binary tree is said to be good if the length of&nbsp;<strong>the shortest path<\/strong>&nbsp;between them is less than or equal to&nbsp;<code>distance<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the number of good leaf node pairs<\/em>&nbsp;in the tree.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/07\/09\/e1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,2,3,null,4], distance = 3\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/07\/09\/e2.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,2,3,4,5,6,7], distance = 3\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> The only good pair is [2,5].\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [100], distance = 1\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,1,1], distance = 2\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The number of nodes in the&nbsp;<code>tree<\/code>&nbsp;is in the range&nbsp;<code>[1, 2^10].<\/code><\/li><li>Each node&#8217;s value is between&nbsp;<code>[1, 100]<\/code>.<\/li><li><code>1 &lt;= distance &lt;= 10<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Brute Force<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346.png\" alt=\"\" class=\"wp-image-7162\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Since n &lt;= 1024, and distance &lt;= 10, we can collect all leaf nodes and try all pairs.<\/p>\n\n\n\n<p>Time complexity: O(|leaves|^2)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int countPairs(TreeNode* root, int distance) {\n    unordered_map<TreeNode*, TreeNode*> parents;\n    vector<TreeNode*> leaves;\n    function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) {\n      if (!c) return;\n      parents[c] = p;      \n      dfs(c->left, c);\n      dfs(c->right, c);\n      if (!c->left && !c->right) leaves.push_back(c);\n    };\n    dfs(root, nullptr);\n    unordered_map<TreeNode*, int> a;\n    auto isGood = [&](TreeNode* n) -> int {\n      for (int i = 0; i < distance &#038;&#038; n; ++i, n = parents[n])\n        if (a.count(n) &#038;&#038; a[n] + i <= distance) return 1;\n      return 0;\n    };\n    int ans = 0;\n    for (int i = 0; i < leaves.size(); ++i) {\n      TreeNode* n1 = leaves[i];\n      a.clear();\n      for (int k = 0; k < distance &#038;&#038; n1; ++k, n1 = parents[n1])\n        a[n1] = k;\n      for (int j = i + 1; j < leaves.size(); ++j)\n        ans += isGood(leaves[j]);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Post order traversal<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-2.png\" alt=\"\" class=\"wp-image-7163\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/07\/1530-ep346-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>For each node, compute the # of good leaf pair under itself.<br>1. count the frequency of leaf node at distance 1, 2, ..., d for both left and right child.<br>2. ans += l[i] * r[j] (i + j &lt;= distance) cartesian product<br>3. increase the distance by 1 for each leaf node when pop<br>Time complexity: O(n*D^2)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countPairs(TreeNode* root, int distance) {\n    int ans = 0;\n    function<vector<int>(TreeNode*)> dfs \n      = [&](TreeNode* c) -> vector<int> {\n      \/\/ f[i] = number of leaves node at distance i.\n      vector<int> f(distance + 1);\n      if (!c) return f;      \n      if (!c->left && !c->right) {        \n        f[0] = 1; \/\/ a single leaf node\n        return f;\n      }\n      const vector<int>& l = dfs(c->left);\n      const vector<int>& r = dfs(c->right);\n      for (int i = 0; i + 1 <= distance; ++i)\n        for (int j = 0; i + j + 2 <= distance; ++j)\n          ans += l[i] * r[j];\n      for (int i = 0; i < distance; ++i)\n        f[i + 1] = l[i] + r[i];\n      return f;\n    };\n    dfs(root);\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  private int D;\n  private int ans;\n  \n  public int countPairs(TreeNode root, int distance) {\n    this.D = distance;\n    this.ans = 0;\n    dfs(root);\n    return ans;\n  }\n  \n  private int[] dfs(TreeNode root) {\n    int[] f = new int[D + 1];\n    if (root == null) return f;\n    if (root.left == null && root.right == null) {\n      f[0] = 1;\n      return f;\n    }\n    int[] fl = dfs(root.left);\n    int[] fr = dfs(root.right);\n    for (int i = 0; i + 1 <= D; ++i)\n      for (int j = 0; i + j + 2 <= D; ++j)\n        this.ans += fl[i] * fr[j];\n    for (int i = 0; i < D; ++i)\n      f[i + 1] = fl[i] + fr[i];\n    return f;\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def countPairs(self, root: TreeNode, D: int) -> int:        \n    def dfs(node):\n      f = [0] * (D + 1)\n      if not node: return f, 0\n      if not node.left and not node.right:\n        f[0] = 1\n        return f, 0      \n      fl, pl = dfs(node.left)\n      fr, pr = dfs(node.right)\n      pairs = 0      \n      for dl, cl in enumerate(fl):\n        for dr, cr in enumerate(fr):          \n          if dl + dr + 2 <= D: pairs += cl * cr\n      for i in range(D):\n        f[i + 1] = fl[i] + fr[i]\n      return f, pl + pr + pairs\n    return dfs(root)[1]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the&nbsp;root&nbsp;of a binary tree and an integer&nbsp;distance. A pair of two different&nbsp;leaf&nbsp;nodes of a binary tree is said to be good if the length&#8230;<\/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":[638,77,177,28],"class_list":["post-7154","post","type-post","status-publish","format-standard","hentry","category-tree","tag-ancestor","tag-graph","tag-medium","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7154","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=7154"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7154\/revisions"}],"predecessor-version":[{"id":7165,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7154\/revisions\/7165"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7154"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7154"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}