在没有递归的情况下查找二叉树的最大深度

Question

查找二叉树最大深度深度的递归机制非常简单,但是如果没有递归,我们怎样才能有效地完成它,因为我有一个大树,我宁愿避免这种递归.

//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的答案.

Answer 1

此变体使用两个堆栈,一个用于explore(wq)的其他节点,另一个包含来自根(path)的当前路径.当我们在两个堆栈的顶部看到相同的节点时,这意味着我们已经探索了它下面的所有内容并且可以弹出它.现在也是更新树深度的时候了.在随机或平衡树上,额外的空间应该是O(log n),当然最坏的情况是O(n).

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++代码http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree- traversal.html不是我声称我是第一个发明它:)