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 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.

• new solution update 2022.05.13

c++

/**
 * 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 {
    string start = "", dest = "";
    string path = "";
    void helper(TreeNode* node, int& s, int& e) {
        if(!node or (start.length() != 0 and dest.length() != 0)) return;
        if(node->val == s) {
            start = path;
        } else if(node->val == e) {
            dest = path;
        }
        path.push_back('L');
        helper(node->left, s, e);
        path.back() = 'R';
        helper(node->right, s, e);
        path.pop_back();
    }
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        helper(root, startValue, destValue);
        string res = "";
        int common = 0;
        for(int i = 0; i < min(start.length(), dest.length()); i++) {
            if(start[i] == dest[i])
                common = i + 1;
            else break;
        }
        start = start.substr(common);
        dest = dest.substr(common);
        for(auto& ch : start)
            ch = 'U';
        return start + dest;
    }
};

• Time : O(v+e)
• Space : O(1)

c++

/**
 * 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* realRoot = NULL;
    int findCount = 0;
    string res;
    void buildGraph(TreeNode* node, int& st, int& dst) {
        if(!node) return;
        int fistCount = findCount;
        if(node->val == st) findCount++;
        if(node->val == dst) findCount++;
        if(findCount == 2) {
            node->left = node->right = NULL;
            return;
        }
        int prevCount = findCount;
        buildGraph(node->left, st, dst);
        if(prevCount == findCount) node->left = NULL;
        else {
            if(findCount == 2 and !fistCount and !realRoot) realRoot = node;
            prevCount = findCount;
        }
        
        if(findCount == 2) {
            node->right = NULL;
            return;   
        }
        buildGraph(node->right, st, dst);
        if(prevCount == findCount) node->right = NULL;
        else {
            if(findCount == 2 and !fistCount and !realRoot) realRoot = node;
        }
    }
    void buildDestToStart(TreeNode* node, int st) {
        if(!node) return;
        if(node->val == st) return;
        res += 'U';
        buildDestToStart(node->left, st);
        buildDestToStart(node->right, st);
    }
    void buildStartToDest(TreeNode* node, int dst) {
        if(node->val == dst) return;
        if(node->left) {
            res += 'L';
            buildStartToDest(node->left, dst);
        } else {
            res += 'R';
            buildStartToDest(node->right, dst);
        }
    }
    bool hasValue(TreeNode* node, int val) {
        if(!node)return false;
        if(node->val == val) return true;
        if(hasValue(node->left, val)) return true;
        return hasValue(node->right, val);
    }
    void buildSearch(int st, int dst) {
        bool leftStart = hasValue(realRoot->left, st);
        if(leftStart) {
            buildDestToStart(realRoot->left, st);
            res += "UR";
            buildStartToDest(realRoot->right, dst);
        } else {
            buildDestToStart(realRoot->right, st);
            res += "UL";
            buildStartToDest(realRoot->left, dst);
        }
    }
    
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        buildGraph(root, startValue, destValue);
        if(realRoot->val == startValue) buildStartToDest(realRoot, destValue);
        else if(realRoot->val == destValue) buildDestToStart(realRoot, startValue);
        else {
            buildSearch(startValue, destValue);
        }

        return res;
    }
};