diff options
-rw-r--r-- | num_good_leaf_node_pair.c | 42 | ||||
-rw-r--r-- | num_good_leaf_node_pair.py | 66 |
2 files changed, 108 insertions, 0 deletions
diff --git a/num_good_leaf_node_pair.c b/num_good_leaf_node_pair.c new file mode 100644 index 0000000..fb80444 --- /dev/null +++ b/num_good_leaf_node_pair.c @@ -0,0 +1,42 @@ +// 1530. Number of Good Leaf Nodes Pairs +#include "leetcode.h" + +/* + * you are 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. + */ + +int dfs(struct TreeNode *root, int distance, int *cnt, int *depth) { + if (!root) + return 0; + if (!root->left && !root->right) { + depth[0] = 1; + return 1; + } + int left_depth[10] = {0}, right_depth[10] = {0}; + int left_cnt = dfs(root->left, distance, cnt, left_depth); + int right_cnt = dfs(root->right, distance, cnt, right_depth); + for (int i = 0; i < 10; i++) + for (int j = 0; j < 10; j++) + if (i + j + 2 <= distance) + *cnt += left_depth[i] * right_depth[j]; + for (int i = 0; i < 9; i++) + depth[i + 1] = left_depth[i] + right_depth[i]; + return left_cnt + right_cnt; +} + +int countPairs(struct TreeNode *root, int distance) { + int ans = 0, depth[10] = {0}; + dfs(root, distance, &ans, depth); + return ans; +} + +int main() { + struct TreeNode *root = treenode_create(1); + root->left = treenode_create(2); + root->right = treenode_create(3); + root->left->left = treenode_create(4); + printf("%d\n", countPairs(root, 3)); // expect: 1 +} diff --git a/num_good_leaf_node_pair.py b/num_good_leaf_node_pair.py new file mode 100644 index 0000000..5115b2a --- /dev/null +++ b/num_good_leaf_node_pair.py @@ -0,0 +1,66 @@ +# 1530. Number of Good Leaf Nodes Pairs +from collections import defaultdict + +""" +you are 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. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def cntPairs(self, root, distance): + """ + :type root: TreeNode + :type distance: int + :rtype: int + """ + graph = defaultdict(list) + + def dfs(node, par=None): + if node: + graph[node].append(par) + graph[par].append(node) + dfs(node.left, node) + dfs(node.right, node) + + dfs(root) + leaves = [] + for node in graph.keys(): + if node and not node.left and not node.right: + leaves.append(node) + cnt = 0 + for leaf in leaves: + queue = [(leaf, 0)] + seen = set(queue) + while queue: + node, length = queue.pop(0) + if length > distance: + break + if node: + for nei in graph[node]: + if nei not in seen: + seen.add(nei) + queue.append((nei, length + 1)) + if ( + node != leaf + and not node.left + and not node.right + and length <= distance + ): + cnt += 1 + return cnt // 2 + + +if __name__ == "__main__": + obj = Solution() + print(obj.cntPairs(root=[1, 2, 3, null, 4], distance=3)) |