Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 16

Description

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 start node s, and a different integer destValue representing the value of the destination node t.

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:

• 'L' means to go from a node to its left child node.
• 'R' means to go from a node to its right child node.
• 'U' means to go from a node to its parent node.

Return the step-by-step directions of the shortest path from node s to node t.

Example 1:

Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: "UURL"
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Example 2:

Input: root = [2,1], startValue = 2, destValue = 1
Output: "L"
Explanation: The shortest path is: 2 → 1.

Constraints:

• The number of nodes in the tree is n.
• 2 <= n <= 105
• 1 <= Node.val <= n
• All the values in the tree are unique.
• 1 <= startValue, destValue <= n
• startValue != destValue

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
  TreeNode *LCA(TreeNode *root, int x, int y) {
    if(!root || root->val == x || root->val == y) return root;
    TreeNode *l = LCA(root->left, x, y);
    TreeNode *r = LCA(root->right, x, y);
    if(!l) return r;
    if(!r) return l;
    return root;
  }
  bool solve(TreeNode* root, int dest, string &path, bool findStart = false) {
    if(!root) return false;
    if(root->val == dest) return true;
    path.push_back(findStart ? 'U' : 'L');
    if(solve(root->left, dest, path, findStart)) return true;
    path.pop_back();
    path.push_back(findStart ? 'U' : 'R');
    if(solve(root->right, dest, path, findStart)) return true;
    path.pop_back();
    return false;
  }
public:
  string getDirections(TreeNode* root, int startValue, int destValue) {
    root = LCA(root, startValue, destValue);
    string from = "";
    string to = "";
    solve(root, startValue, from, true);
    solve(root, destValue, to);
    return from + to;
  }
};