aboutsummaryrefslogtreecommitdiff
path: root/cousins_binary_tree2.c
blob: 5d3c5160ea32e97ecdbdcdabf2ceae1b0e4894f4 (plain)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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);
}