diff options
author | Jack Sangdahl <[email protected]> | 2024-10-22 18:26:28 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-22 18:26:28 -0600 |
commit | 9b1afed7980a5eb2b1f4bd886d07340629fde40c (patch) | |
tree | 81adc5698b6946f2dbb17894e3e032f5a215a649 | |
parent | c6245c8eb0b1d8463bb3f5d2d1349c7de10a1c32 (diff) | |
download | leetcode-9b1afed7980a5eb2b1f4bd886d07340629fde40c.tar.gz leetcode-9b1afed7980a5eb2b1f4bd886d07340629fde40c.zip |
2641. cousins in binary tree 2
-rw-r--r-- | cousins_binary_tree2.c | 61 | ||||
-rw-r--r-- | cousins_binary_tree2.py | 58 |
2 files changed, 119 insertions, 0 deletions
diff --git a/cousins_binary_tree2.c b/cousins_binary_tree2.c new file mode 100644 index 0000000..5d3c516 --- /dev/null +++ b/cousins_binary_tree2.c @@ -0,0 +1,61 @@ +// 2641. Cousins in Binary Tree II +#include "leetcode.h" + +/* + * given the 'root' of a binary tree, replace the value of each node in the tree + * with the sum of all its cousins' values. two nodes of a binary tree are + * cousins if they have the same depth with different paths. return 'root' of + * the modified tree. note that the depth of a nodie is a number of edges in the + * path from the root node to it. + */ + +void dfs1(struct TreeNode *root, int *sum, int idx) { + if (!root) + return; + sum[idx] += root->val; + dfs1(root->left, sum, idx + 1); + dfs1(root->right, sum, idx + 1); +} + +int dfs2(struct TreeNode *root, int *sum, int idx) { + if (!root) + return 0; + int l = dfs2(root->left, sum, idx + 1); + int r = dfs2(root->right, sum, idx + 1); + if (l && !r) + root->left->val = sum[idx + 1] - l; + if (!l && r) + root->right->val = sum[idx + 1] - r; + if (l && r) { + root->left->val = sum[idx + 1] - r - l; + root->right->val = sum[idx + 1] - r - l; + } + return root->val; +} + +struct TreeNode *replaceValueInTree(struct TreeNode *root) { + int *sum = (int *)calloc(100000, sizeof(int)); + dfs1(root, sum, 0); + root->val -= dfs2(root, sum, 0); + free(sum); + return root; +} + +int main() { + struct TreeNode *r1 = treenode_create(5); + r1->left = treenode_create(4); + r1->right = treenode_create(9); + r1->left->left = treenode_create(10); + r1->left->right = treenode_create(10); + r1->right->left = NULL; + r1->right->right = treenode_create(7); + struct TreeNode *r2 = treenode_create(3); + r2->left = treenode_create(2); + r2->right = treenode_create(1); + struct TreeNode *rvit1 = replaceValueInTree(r1); + struct TreeNode *rvit2 = replaceValueInTree(r2); + treenode_print(rvit1); // expect : 0 0 0 7 7 null 11 + treenode_print(rvit2); // expect: 0 0 0 + treenode_free(r1), treenode_free(rvit1); + treenode_free(r2), treenode_free(rvit2); +} diff --git a/cousins_binary_tree2.py b/cousins_binary_tree2.py new file mode 100644 index 0000000..23e56d5 --- /dev/null +++ b/cousins_binary_tree2.py @@ -0,0 +1,58 @@ +# 2641. Cousins in Binary Tree II +from collections import Counter + +""" +given the 'root' of a binary tree, replace the value of each node in the tree +with the sum of all its cousins' values. two nodes of a binary tree are +cousins if they have the same depth with different paths. return 'root' of +the modified tree. note that the depth of a nodie is a number of edges in the +path from the root node to it. +""" + + +# 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 replaceValueInTree(self, root): + """ + :type root: Optional[TreeNode] + :rtype: Optional[TreeNode] + """ + sum = Counter() + + def dfs1(r, l): + if not r: + return + sum[l] += r.val + dfs1(r.left, l + 1) + dfs1(r.right, l + 1) + + dfs1(root, 0) + + def dfs2(r, l, curr): + cousin_sum = ( + sum[l + 1] + - (r.left.val if r.left else 0) + - (r.right.val if r.right else 0) + ) + if r.left: + curr.left = TreeNode(cousin_sum) + dfs2(r.left, l + 1, curr.left) + if r.right: + curr.right = TreeNode(cousin_sum) + dfs2(r.right, l + 1, curr.right) + return curr + + return dfs2(root, 0, TreeNode(0)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.replaceValueInTree(root=[5, 4, 9, 1, 10, None, 7])) + print(obj.replaceValueInTree(root=[3, 1, 2])) |