Re: [閒聊] 每日leetcode

[smart0eddie (smart0eddie)]

2024-07-16
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.

分別找root 到兩個目標數的兩條path
然後把共通的點砍掉
root2src 的全部改成 U
兩條串起來就是答案
然後我想兩條一次找完 用DFS走
可能stack 操作太多了 速度有點慢
兩條分開走可能反而可以簡化一些東西

/**
 * 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 {
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        string cur_path = "";
        vector<TreeNode*> nodes(1, root);
        unordered_set<int> visited;
        string path1;
        string path2;
        bool found1 = false;
        bool found2 = false;

        // DFS to find both path
        while(!nodes.empty() && !(found1 && found2)) {
            // visit
            TreeNode*& cur = nodes.back();
            visited.insert(cur->val);

            if (!found1 && cur->val == startValue) {
                found1 = true;
                path1 = cur_path;
            }
            if (!found2 && cur->val == destValue) {
                found2 = true;
                path2 = cur_path;
            }

            // next
            if (cur->left && !visited.contains(cur->left->val)) {
                cur_path.push_back('L');
                nodes.push_back(cur->left);
            }
            else if (cur->right && !visited.contains(cur->right->val)) {
                cur_path.push_back('R');
                nodes.push_back(cur->right);
            }
            else {
                cur_path.pop_back();
                nodes.pop_back();
            }
        }

        //skip common path
        int common = 0;
        while (common < path1.size() && common < path2.size() &&
path1[common] == path2[common]) {
            common++;
        }

        string result = string(path1.size()-common, 'U') +
path2.substr(common);

        return result;
    }

private:

};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721100339.A.34A.html
→ CanIndulgeMe: 技術大神
推 dont: 大師