aboutsummaryrefslogtreecommitdiff
path: root/amount_time_bt_infect.c
diff options
context:
space:
mode:
Diffstat (limited to 'amount_time_bt_infect.c')
-rw-r--r--amount_time_bt_infect.c84
1 files changed, 84 insertions, 0 deletions
diff --git a/amount_time_bt_infect.c b/amount_time_bt_infect.c
new file mode 100644
index 0000000..6af96e1
--- /dev/null
+++ b/amount_time_bt_infect.c
@@ -0,0 +1,84 @@
+// 2385. Amount of Time for Binary Tree to Be Infected
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree with unique values, and an integer 'start'.
+ * at minute 0, an infection starts from the node with value 'start' each
+ * minute, a node becomes infected if the node is currently uninfected, or the
+ * node is adjacent to an infected node. return the number of minutes needed for
+ * the entire tree to be infected.
+ */
+
+struct TreeNode {
+ int val;
+ struct TreeNode *left;
+ struct TreeNode *right;
+};
+
+int depthAndFindVal(struct TreeNode *root, int val, bool *exist,
+ int *height_start) {
+ if (!root)
+ return -1;
+ int height = 1 + fmax(depthAndFindVal(root->left, val, exist, height_start),
+ depthAndFindVal(root->right, val, exist, height_start));
+ if (root->val == val) {
+ *exist = true;
+ *height_start = height;
+ }
+ return height;
+}
+
+int depth(struct TreeNode *root) {
+ if (!root)
+ return -1;
+ return 1 + fmax(depth(root->left), depth(root->right));
+}
+
+void findPath(struct TreeNode *root, int start, struct TreeNode **data,
+ int data_idx, struct TreeNode **path, int *path_idx) {
+ if (!root)
+ return;
+ data[data_idx] = root;
+ if (root->val == start) {
+ *path_idx = data_idx + 1;
+ for (int i = 0; i < *path_idx; i++)
+ path[i] = data[i];
+ return;
+ }
+ findPath(root->left, start, data, data_idx + 1, path, path_idx);
+ findPath(root->right, start, data, data_idx + 1, path, path_idx);
+}
+
+int amountOfTime(struct TreeNode *root, int start) {
+ bool left_exist = false, right_exist = false;
+ int height_start = 0, data_idx = 0, path_idx = 0, ans;
+
+ int left_height =
+ depthAndFindVal(root->left, start, &left_exist, &height_start) + 1;
+ int right_height =
+ depthAndFindVal(root->right, start, &right_exist, &height_start) + 1;
+
+ if (root->val == start)
+ return fmax(left_height, right_height);
+
+ int n = fmax(left_height, right_height);
+ struct TreeNode **data = malloc(n * sizeof(struct TreeNode *));
+ struct TreeNode **path = malloc(n * sizeof(struct TreeNode *));
+ struct TreeNode *tmp = left_exist ? root->left : root->right;
+ findPath(tmp, start, data, data_idx, path, &path_idx);
+ ans = left_exist ? right_height + path_idx : left_height + path_idx;
+
+ int start_height = depth(path[path_idx - 1]);
+ ans = fmax(ans, start_height);
+ int k = 1;
+ for (int i = path_idx - 2; i >= 0; i--) {
+ int d;
+ if (path[i]->left == path[i + 1])
+ d = depth(path[i]->right);
+ else
+ d = depth(path[i]->left);
+ ans = fmax(ans, d + 1 + k);
+ k++;
+ }
+ return ans;
+}