Given the root
of a binary tree and an integer distance
. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance
.
Return the number of good leaf node pairs in the tree.
Example 1:
Input: root = [1,2,3,null,4], distance = 3 Output: 1 Explanation: 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.
Example 2:
Input: root = [1,2,3,4,5,6,7], distance = 3 Output: 2 Explanation: 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.
Example 3:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3 Output: 1 Explanation: The only good pair is [2,5].
Example 4:
Input: root = [100], distance = 1 Output: 0
Example 5:
Input: root = [1,1,1], distance = 2 Output: 1
Constraints:
- The number of nodes in the
tree
is in the range[1, 2^10].
- Each node’s value is between
[1, 100]
. 1 <= distance <= 10
Solution: Brute Force
Since n <= 1024, and distance <= 10, we can collect all leaf nodes and try all pairs.
Time complexity: O(|leaves|^2)
Space complexity: O(n)
C++
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 |
class Solution { public: int countPairs(TreeNode* root, int distance) { unordered_map<TreeNode*, TreeNode*> parents; vector<TreeNode*> leaves; function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) { if (!c) return; parents[c] = p; dfs(c->left, c); dfs(c->right, c); if (!c->left && !c->right) leaves.push_back(c); }; dfs(root, nullptr); unordered_map<TreeNode*, int> a; auto isGood = [&](TreeNode* n) -> int { for (int i = 0; i < distance && n; ++i, n = parents[n]) if (a.count(n) && a[n] + i <= distance) return 1; return 0; }; int ans = 0; for (int i = 0; i < leaves.size(); ++i) { TreeNode* n1 = leaves[i]; a.clear(); for (int k = 0; k < distance && n1; ++k, n1 = parents[n1]) a[n1] = k; for (int j = i + 1; j < leaves.size(); ++j) ans += isGood(leaves[j]); } return ans; } }; |
Solution 2: Post order traversal
For each node, compute the # of good leaf pair under itself.
1. count the frequency of leaf node at distance 1, 2, …, d for both left and right child.
2. ans += l[i] * r[j] (i + j <= distance) cartesian product
3. increase the distance by 1 for each leaf node when pop
Time complexity: O(n*D^2)
Space complexity: O(n)
C++
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 |
// Author: Huahua class Solution { public: int countPairs(TreeNode* root, int distance) { int ans = 0; function<vector<int>(TreeNode*)> dfs = [&](TreeNode* c) -> vector<int> { // f[i] = number of leaves node at distance i. vector<int> f(distance + 1); if (!c) return f; if (!c->left && !c->right) { f[0] = 1; // a single leaf node return f; } const vector<int>& l = dfs(c->left); const vector<int>& r = dfs(c->right); for (int i = 0; i + 1 <= distance; ++i) for (int j = 0; i + j + 2 <= distance; ++j) ans += l[i] * r[j]; for (int i = 0; i < distance; ++i) f[i + 1] = l[i] + r[i]; return f; }; dfs(root); return ans; } }; |
Java
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 |
class Solution { private int D; private int ans; public int countPairs(TreeNode root, int distance) { this.D = distance; this.ans = 0; dfs(root); return ans; } private int[] dfs(TreeNode root) { int[] f = new int[D + 1]; if (root == null) return f; if (root.left == null && root.right == null) { f[0] = 1; return f; } int[] fl = dfs(root.left); int[] fr = dfs(root.right); for (int i = 0; i + 1 <= D; ++i) for (int j = 0; i + j + 2 <= D; ++j) this.ans += fl[i] * fr[j]; for (int i = 0; i < D; ++i) f[i + 1] = fl[i] + fr[i]; return f; } } |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua class Solution: def countPairs(self, root: TreeNode, D: int) -> int: def dfs(node): f = [0] * (D + 1) if not node: return f, 0 if not node.left and not node.right: f[0] = 1 return f, 0 fl, pl = dfs(node.left) fr, pr = dfs(node.right) pairs = 0 for dl, cl in enumerate(fl): for dr, cr in enumerate(fr): if dl + dr + 2 <= D: pairs += cl * cr for i in range(D): f[i + 1] = fl[i] + fr[i] return f, pl + pr + pairs return dfs(root)[1] |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment