# Iteration version DFS

• My first thought was to use recursive backtracking. Since the largest size is 10^4, it would overflow the stack with recursive method. So I simply convert the recursive version into iterative version. Maybe this is why BFS is much simpler. This is just for illustration. Code is tediously long.

``````public boolean sequenceReconstruction(int[] org, int[][] seqs) {
if (seqs.length == 0)
return false;
Map<Integer, List<Integer>> edges = new HashMap<>();
boolean[] hasParents = new boolean[org.length + 1];
for (int row = 0 ; row < seqs.length ; row ++) {
for (int col = 0 ; col < seqs[row].length ; col ++) {
if (seqs[row][col] > org.length || seqs[row][col] <= 0)
return false;
if (col > 0)
hasParents[seqs[row][col]] = true;
if (!edges.containsKey(seqs[row][col]))
edges.put(seqs[row][col], new ArrayList<>());
if (col <= seqs[row].length - 2)
}
}
int root = -1;
int countOfRoots = 0;
for (int i = 1 ; i < hasParents.length ; i ++) {
if (!hasParents[i]) {
root = i;
countOfRoots ++;
}
}
if (countOfRoots != 1)
return false;

int countOfOrders = 0;
int[] resOrder = new int[org.length];
int[] aux = new int[org.length];
Stack<MyClass> stack = new Stack<>();
stack.push(new MyClass(root, 0));
while (!stack.empty()) {
MyClass cur = stack.pop();
if (cur.depth >= resOrder.length) {
return false;
}
aux[cur.depth] = cur.val;
List<Integer> chil = edges.get(cur.val);
if (chil.size() == 0) {
if (cur.depth == resOrder.length - 1) {
if (countOfOrders == 0) {
for (int chck = 0 ; chck < resOrder.length ; chck ++) {
resOrder[chck] = aux[chck];
}
countOfOrders ++;
} else {
for (int chck = 0 ; chck < resOrder.length ; chck ++) {
if (resOrder[chck] != aux[chck]) {
return false;
}
}
}
}
}
for (Integer next : chil) {
MyClass nextChil = new MyClass(next, cur.depth + 1);
stack.push(nextChil);
}
}
for (int i = 0 ; i < resOrder.length ; i ++) {
if (org[i] != resOrder[i]) {
return false;
}
}
return true;
}
private class MyClass {
int val;
int depth;
public MyClass(int newVal, int newDepth){
val = newVal;
depth = newDepth;
}
}``````

• what conditions you used in the DFS to check validation?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.