솔루션: 선주문 순회와 일치하도록 이진 트리 뒤집기

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #971(중간): 선주문 순회와 일치하도록 이진 트리 뒤집기

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.

Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:

Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.

Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].

예:

Example 1:
Input:	root = [1,2], voyage = [2,1]
Output:	[-1]
Visual:
Explanation:	It is impossible to flip the nodes such that the pre-order traversal matches voyage.

Example 2:
Input:	root = [1,2,3], voyage = [1,3,2]
Output:	[1]
Visual:
Explanation:	Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.

Example 3:
Input:	root = [1,2,3], voyage = [1,2,3]
Output:	[]
Visual:
Explanation:	The tree's pre-order traversal already matches voyage, so no nodes need to be flipped.

제약:

• The number of nodes in the tree is n.
• n == voyage.length
• 1 <= n <= 100
• 1 <= Node.val, voyage[i] <= n
• All the values in the tree are unique.
• All the values in voyage are unique.

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

뒤집혀야 하는 노드를 찾기 위해 DFS(깊이 우선 검색)의 한 형태인 사전 순회에서 루트에서 이진 트리를 탐색하고 노드 값을 값과 비교해야 합니다. 항해 배열(V)에서.

대부분의 이진 트리 DFS 솔루션과 마찬가지로 일반적인 솔루션은 재귀 접근 방식을 사용합니다. 이진 트리를 통과할 때 V의 현재 인덱스에 대한 인덱스 카운터(vix)뿐만 아니라 뒤집힌 노드를 저장하기 위해 최상위 범위 응답 배열(ans)을 사용할 수 있습니다.

재귀 함수(dfs)의 경우 재귀 함수가 null 노드에 도달하거나 이미 오류를 발견한 경우 종료 조건을 먼저 처리해야 합니다. 그런 다음 노드 값이 예상한 값이 아닌 경우 답을 [-1]로 설정해야 합니다.

필요한 뒤집기를 결정할 때 부모 수준 액세스 권한이 필요하므로 다음 재귀 라운드를 호출하기 전에 지금 처리해야 합니다. V의 다음 인덱스에 대해 왼쪽 노드 값을 간단히 확인할 수 있으며 일치하지 않는 경우 ans를 업데이트하여 플립을 설명해야 합니다.

그러나 이진 트리의 노드를 실제로 뒤집는 대신 두 분기를 역순으로 반복하여 뒤집기를 시뮬레이션할 수 있습니다. 그렇지 않으면 정상적인 선주문 순회를 진행할 수 있습니다.

구현:

Python은 최상위 범위 변수를 쉽게 다루지 않으므로 ans 배열의 첫 번째 요소를 V 인덱스(vix)로 사용한 다음 재귀 함수에서 ans에 대한 참조를 전달할 수 있습니다.

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

const flipMatchVoyage = function (root, V) {
    let ans = [], vix = 0
    const dfs = node => {
        if (!node || ans[0] === -1) return
        if (node.val !== V[vix++]) ans = [-1]
        else if (node.left && node.left.val !== V[vix]) {
            ans.push(node.val)
            dfs(node.right)
            dfs(node.left)
        } else {
            dfs(node.left)
            dfs(node.right)
        }
    }
    dfs(root)
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def flipMatchVoyage(self, root: TreeNode, V: List[int]) -> List[int]:
        ans = [0]
        def dfs(node, V, ans):
            if not node or ans[0] == -1: return
            if node.val != V[ans[0]]: ans[0] = -1
            else:
                ans[0] += 1
                if node.left and node.left.val != V[ans[0]]:
                    ans.append(node.val)
                    dfs(node.right, V, ans)
                    dfs(node.left, V, ans)
                else:
                    dfs(node.left, V, ans)
                    dfs(node.right, V, ans)
        dfs(root, V, ans)
        return ans[:1] if ans[0] == -1 else ans[1:]

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    int vix = 0;
    List<Integer> ans = new ArrayList<>();
    private void dfs(TreeNode node, int[] V) {
        if (node == null || (ans.size() != 0 && ans.get(0) == -1)) return;
        if (node.val != V[vix++])
            ans = new ArrayList<Integer>(Arrays.asList(-1));
        else if (node.left != null && node.left.val != V[vix]) {
            ans.add(node.val);
            dfs(node.right, V);
            dfs(node.left, V);
        } else {
            dfs(node.left, V);
            dfs(node.right, V);
        }
    }
    public List<Integer> flipMatchVoyage(TreeNode root, int[] V) {
        dfs(root, V);
        return ans;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    int vix = 0;
    vector<int> ans;
    void dfs(TreeNode* node, vector<int>& V) {
        if (!node || (ans.size() && ans[0] == -1)) return;
        if (node->val != V[vix++]) ans = {-1};
        else if (node->left && node->left->val != V[vix]) {
            ans.push_back(node->val);
            dfs(node->right, V);
            dfs(node->left, V);
        } else {
            dfs(node->left, V);
            dfs(node->right, V);
        }
    }
public:
    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& V) {
        dfs(root, V);
        return ans;
    }
};