寻找二叉树的最大深度没有递归 [英] Finding max depth of binary tree without recursion

问题描述

递归机制来找到二进制树的深度最大深度是非常简单的，但如何才能有效地做到这一点没有递归，因为我有棵大树，我宁愿避免这种递归。

Recursive mechanism to find max depth of depth of binary tree is very straightforward, but how can we do it efficiently without recursion as I have large tree where I would rather avoid this recursion.

//Recursive mechanism which I want to replace with non-recursive
private static int maxDepth(Node node) {
if (node == null) return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right)); 
}

PS：我要寻找一个在Java的答案

PS: I am looking for answers in Java.

推荐答案

这个版本，采用两个堆栈，一个用于其他节点探索（ WQ ）和一个总是包含从根电流路径（路径）。当我们看到两个顶部的同一个节点堆叠这意味着我们已经探索它下面的一切，可以弹出它。这是为了太更新树深度的时间。在随机或平衡树额外的空间应该是O（log n）的，在最坏情况下为O（n），当然。

This variant uses two stacks, one for additional nodes to explore (wq) and one always containing the current path from the root (path). When we see the same node on the top of both stacks it means we've explored everything below it and can pop it. This is the time to update the tree depth too. On random or balanced trees the additional space should be O(log n), in the worst case O(n), of course.

static int maxDepth (Node r) {
    int depth = 0;
    Stack<Node> wq = new Stack<>();
    Stack<Node> path = new Stack<>();

    wq.push (r);
    while (!wq.empty()) {
        r = wq.peek();
        if (!path.empty() && r == path.peek()) {
            if (path.size() > depth)
                depth = path.size();
            path.pop();
            wq.pop();
        } else {
            path.push(r);
            if (r.right != null)
                wq.push(r.right);
            if (r.left != null)
                wq.push(r.left);
        }
    }

    return depth;
}

（无耻插头：我有这个想法，使用双协议栈的非递归遍历几个星期前，查了C ++ code此处<一个href="http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree-traversal.html">http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree-traversal.html不是我要求我是第一个去创造吧：）

(Shameless plug: I had this idea for using dual stacks for non-recursive traversals a few weeks ago, check for a C++ code here http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree-traversal.html not that I claim I was the first to invent it :)

这篇关于寻找二叉树的最大深度没有递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！