[LeetCode] 2096. Step-By-Step Directions From a Binary Tree Node to Another

https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/

leetcode - Step-By-Step Directions From a Binary Tree Node to Another

문제 유형 : 이진트리, 재귀, 백트래킹

문제 난이도 : Medium

 

문제

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.

 

이진트리의 루트와 정수 startValue, destValue가 주어진다.

startValue에서 destValue까지 가기 위한 최소 이동 연산을 문자열로 표현하시오.

연산은 다음과 같습니다.

• 'L': 왼쪽자식으로 이동
• 'R': 오른쪽 자식으로 이동
• 'U': 부모노드로 이동

 

풀이

두 노드의 공통된 조상노드를 찾는다.

공통된 조상노드를 찾는 방법은 다음과 같다:

현재 노드가 두 노드 중 하나 또는 null이면, 현재 노드를 반환한다.

그게 아니라면, 양쪽 서브트리를 순회한다.

만약 양쪽 서브트리에서 둘다 유효한 노드를 찾으면, 현재 서브트리의 루트가 공통조상이다.

아니면, 둘 중에서 유효한 노드를 반환한다.

 

이제 공통조상과 각 노드로의 루트를 구하면 된다.

백트래킹을 통해서 움직인 루트를 구할 수 있다.

startValue에서 공통조상으로 이동하는 경로는 모두 'U'로 치환시키고 두 루트를 접합시켜서 반환한다.

 

코드

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 {
public:
    TreeNode* findCommonAncestor(TreeNode* root, int a, int b) {
        if(!root || root -> val == a || root -> val == b) return root;

        auto left = findCommonAncestor(root -> left, a, b);
        auto right = findCommonAncestor(root -> right, a, b);
        if(left && right) {
            return root;
        }
        return left? left : right;
    }

    bool getRoute(TreeNode* root, int target, string &route) {
        if(!root) return false;
        if(root -> val == target) return true;

        route.push_back('L');
        if(getRoute(root -> left, target, route)) return true;
        route.pop_back();

        route.push_back('R');
        if(getRoute(root -> right, target, route)) return true;
        route.pop_back();

        return false;
    }

    string getDirections(TreeNode* root, int startValue, int destValue) {
        string srcToRoot;
        string rootToDst;
        auto CA = findCommonAncestor(root, startValue, destValue);
        getRoute(CA, startValue, srcToRoot);
        getRoute(CA, destValue, rootToDst);

        for(int i = 0; i < srcToRoot.size(); i++) {
            srcToRoot[i] = 'U';
        }
        return srcToRoot + rootToDst;
    }
};