diff options
Diffstat (limited to 'num_good_leaf_node_pair.c')
-rw-r--r-- | num_good_leaf_node_pair.c | 42 |
1 files changed, 42 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 +} |