有什么方法可以将深度/级别存储在级别的哈希图和节点迭代深度优先搜索的数组列表中?

Question

我知道这是某种编码挑战，我试图解决一个问题，我用BFS解决了它，但我也想用dfs解决它。那么有没有办法在迭代DFS中使用node存储深度，我知道这可以使用递归轻松实现。这是我的进步：

public HashMap<Integer, ArrayList<TreeNode>> getUsingDFS(TreeNode root){
HashMap<Integer, ArrayList<TreeNode>> map = new HashMap();

List<TreeNode> visited = new ArrayList();

Stack<TreeNode> stack = new Stack();
stack.add(root);
int level = 0;

int top = 1;

while(!stack.isEmpty()){
TreeNode tempNode = stack.pop();
//level / depth store here.
map.put(level, map.getOrDefault(level, new ArrayList()).add(tempNode));


visited.add(tempNode);

if(tempNode.left != null){
queue.add(tempNode.left);
}

if(tempNode.right != null){
queue.add(tempNode.right);
}


}
}

Answer 1

这是我如何实现这一目标的。

public HashMap<Integer, ArrayList<LevelNode>> getUsingDFS(TreeNode root){
HashMap<Integer, ArrayList<LevelNode>> map = new HashMap();

Queue<LevelNode> queue = new LinkedList();
queue.add(new LevelNode(root, 0));

while(!queue.isEmpty()){
LevelNode tempNode = queue.poll();

ArrayList<LevelNode> list = map.getOrDefault(tempNode.level, new ArrayList());
list.add(tempNode);

map.put(tempNode.level, list);

if(tempNode.node.left != null){
queue.add(new LevelNode(tempNode.node.left, tempNode.level+1));
}

if(tempNode.node.right != null){
queue.add(new LevelNode(tempNode.node.right, tempNode.level+1));
}
}
return map;
}
class LevelNode{
TreeNode node;
int level;

LevelNode(TreeNode node, int level){
this.level = level;
this.node = node;
}
}