diff options
-rw-r--r-- | step_by_step_dir_bt.c | 73 | ||||
-rw-r--r-- | step_by_step_dir_bt.py | 85 |
2 files changed, 158 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 +} diff --git a/step_by_step_dir_bt.py b/step_by_step_dir_bt.py new file mode 100644 index 0000000..4c5791f --- /dev/null +++ b/step_by_step_dir_bt.py @@ -0,0 +1,85 @@ +# 2096. Step-By-Step Directions From a Binary Tree Node to Another + +""" +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. +""" + + +# 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 getDirections(self, root, startValue, destValue): + """ + :type root: Optional[TreeNode] + :type startValue: int + :type destValue: int + :rtype: str + """ + q = list[TreeNode] = [root] + while q: + curr_node: TreeNode = q.pop() + if curr_node.val == startValue: + start_node = curr_node + break + if curr_node.left: + q.append(curr_node.left) + if curr_node.right: + q.append(curr_node.right) + nodes_parents: dict[int, TreeNode] = {} + q = [root] + while q: + curr_node = q.pop() + if curr_node.left: + nodes_parents[curr_node.left.val] = curr_node + q.append(curr_node.left) + if curr_node.right: + nodes_parents[curr_node.right.val] = curr_node + q.append(curr_node.right) + visited = set() + q = [start_node] + tracked_path: dict[TreeNode, tuple(TreeNode, str)] = {} + while q: + curr_node = q.pop() + visited.add(curr_node) + if curr_node.val == destValue: + destination_node = curr_node + break + if ( + curr_node.val in nodes_parents + and nodes_parents[curr_node.val] not in visited + ): + parent = nodes_parents[curr_node.val] + q.append(parent) + tracked_path[parent] = (curr_node, "U") + if curr_node.left and curr_node.left not in visited: + q.append(curr_node.left) + tracked_path[curr_node.left] = (curr_node, "L") + if curr_node.right and curr_node.right not in visited: + q.append(curr_node.right) + tracked_path[curr_node.right] = (curr_node, "R") + ans = list[str] = [] + curr_node = destination_node + while curr_node != start_node: + source_node, direction = tracked_path[curr_node] + ans.append(direction) + curr_node = source_node + ans.reverse() + return "".join(ans) + + +if __name__ == "__main__": + obj = Solution() + print(obj.getDirections(root=[5, 1, 2, 3, null, 6, 4], startValue=3, destValue=6)) + print(obj.getDirections(root=[2, 1], startValue=2, destValue=1)) |