aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-22 18:26:28 -0600
committerJack Sangdahl <[email protected]>2024-10-22 18:26:28 -0600
commit9b1afed7980a5eb2b1f4bd886d07340629fde40c (patch)
tree81adc5698b6946f2dbb17894e3e032f5a215a649
parentc6245c8eb0b1d8463bb3f5d2d1349c7de10a1c32 (diff)
downloadleetcode-9b1afed7980a5eb2b1f4bd886d07340629fde40c.tar.gz
leetcode-9b1afed7980a5eb2b1f4bd886d07340629fde40c.zip
2641. cousins in binary tree 2
-rw-r--r--cousins_binary_tree2.c61
-rw-r--r--cousins_binary_tree2.py58
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]))