2096. Step-By-Step Directions From a Binary Tree Node to Another Medium

1/**
2 * [2096] Step-By-Step Directions From a Binary Tree Node to Another
3 *
4 * 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 start node s, and a different integer destValue representing the value of the destination node t.
5 * Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
6 * 
7 * 	'L' means to go from a node to its left child node.
8 * 	'R' means to go from a node to its right child node.
9 * 	'U' means to go from a node to its parent node.
10 * 
11 * Return the step-by-step directions of the shortest path from node s to node t.
12 *  
13 * Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;" />
15 * Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
16 * Output: "UURL"
17 * Explanation: The shortest path is: 3 &rarr; 1 &rarr; 5 &rarr; 2 &rarr; 6.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;" />
21 * Input: root = [2,1], startValue = 2, destValue = 1
22 * Output: "L"
23 * Explanation: The shortest path is: 2 &rarr; 1.
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	The number of nodes in the tree is n.
29 * 	2 <= n <= 10^5
30 * 	1 <= Node.val <= n
31 * 	All the values in the tree are unique.
32 * 	1 <= startValue, destValue <= n
33 * 	startValue != destValue
34 * 
35 */
36pub struct Solution {}
37use crate::util::tree::{TreeNode, to_tree};
38
39// problem: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
40// discuss: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44// Definition for a binary tree node.
45// #[derive(Debug, PartialEq, Eq)]
46// pub struct TreeNode {
47//   pub val: i32,
48//   pub left: Option<Rc<RefCell<TreeNode>>>,
49//   pub right: Option<Rc<RefCell<TreeNode>>>,
50// }
51// 
52// impl TreeNode {
53//   #[inline]
54//   pub fn new(val: i32) -> Self {
55//     TreeNode {
56//       val,
57//       left: None,
58//       right: None
59//     }
60//   }
61// }
62use std::rc::Rc;
63use std::cell::RefCell;
64impl Solution {
65    pub fn get_directions(root: Option<Rc<RefCell<TreeNode>>>, start_value: i32, dest_value: i32) -> String {
66        String::new()
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_2096() {
78    }
79}
80