Video Solution

By David Zhou

Official Analysis (C++)

Explanation

To satisfy the BFS order, we can connect node 1 to every other node, placing them all at the same level. This guarantees the correct BFS traversal.

To satisfy the DFS order, we can form a simple path starting from node 1 by connecting each node to the next in the DFS list. This ensures a valid DFS traversal.

We construct the edge list by:

• Adding edges from node 1 to every other node in the BFS list.
• Adding edges between each consecutive pair in the DFS list.

If both traversals list a different second node, there's no valid graph, as the first child of node 1 must be the same in both traversals.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> bfs(n);
	vector<int> dfs(n);
	for (int i = 0; i < n; i++) { cin >> bfs[i]; }

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] bfs = new int[n];
		int[] dfs = new int[n];

Copy
n = int(input())
bfs = list(map(int, input().split()))
dfs = list(map(int, input().split()))

if n == 1:
	print(0)
	exit()

# first child of node 1 must match
if bfs[1] != dfs[1]: