aboutsummaryrefslogtreecommitdiff
path: root/step_by_step_dir_bt.c
diff options
context:
space:
mode:
Diffstat (limited to 'step_by_step_dir_bt.c')
-rw-r--r--step_by_step_dir_bt.c73
1 files changed, 73 insertions, 0 deletions
diff --git a/step_by_step_dir_bt.c b/step_by_step_dir_bt.c
new file mode 100644
index 0000000..9159830
--- /dev/null
+++ b/step_by_step_dir_bt.c
@@ -0,0 +1,73 @@
+// 2096. Step-By-Step Directions From a Binary Tree Node to Another
+#include "leetcode.h"
+
+/*
+ * you are given the 'root' of a binary tree with 'n' nodes. each node is
+ * uniquely assigned a value from 1 to 'n'. you are also given an integer
+ * 'startValue' representing the value of the stat node 's', nd a different
+ * integer 'destValue' representing the value of the destination node 't', find
+ * the shortest path from node 's' to node 't'. generate step by step directions
+ * of such path as a string consisting only of upper case letters L R and U,
+ * return the step by step directions of the shortest path.
+ */
+
+void reverse_str(char *s) {
+ int tmp;
+ for (int i = 0; i < strlen(s) / 2; i++) {
+ tmp = s[i];
+ s[i] = s[strlen(s) - 1 - i];
+ s[strlen(s) - 1 - i] = tmp;
+ }
+}
+
+int find_node(struct TreeNode *root, int val, char *s) {
+ if (!root)
+ return 0;
+ if (root->val == val)
+ return 1;
+ int res = find_node(root->left, val, s);
+ if (res == 1) {
+ strcat(s, "L");
+ return 1;
+ }
+ res = find_node(root->right, val, s);
+ if (res == 1) {
+ strcat(s, "R");
+ return 1;
+ }
+ return 0;
+}
+
+#define MAX_SZ 10001
+
+char *getDirections(struct TreeNode *root, int startValue, int destValue) {
+ char str_s[MAX_SZ] = "", str_d[MAX_SZ] = "";
+ char *ans = (char *)malloc(MAX_SZ * sizeof(char));
+ ans[0] = '\0';
+ find_node(root, startValue, str_s);
+ find_node(root, destValue, str_d);
+ int s_idx = strlen(str_s) - 1, d_idx = strlen(str_d) - 1;
+ while (s_idx >= 0 && d_idx >= 0) {
+ if (str_s[s_idx] == str_d[d_idx]) {
+ str_s[s_idx] = '\0';
+ str_d[d_idx] = '\0';
+ s_idx--, d_idx--;
+ } else
+ break;
+ }
+ for (int i = 0; i <= s_idx; i++)
+ strcat(ans, "U");
+ reverse_str(str_d);
+ strcat(ans, str_d);
+ return ans;
+}
+
+int main() {
+ struct TreeNode *root = treenode_create(5);
+ root->left = treenode_create(1);
+ root->right = treenode_create(2);
+ root->left->left = treenode_create(3);
+ root->right->left = treenode_create(6);
+ root->right->right->right = treenode_create(4);
+ printf("%s\n", getDirections(root, 3, 6)); // expect: UURL
+}