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

一尘不染

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

algorithm

查找二叉树最大深度的递归机制非常简单，但是如果没有递归，我们如何有效地做到这一点，因为我有一个大树，我宁愿避免这种递归。

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

阅读 246

2020-07-28

共1个答案

一尘不染

此变体使用两个堆栈，一个用于其他节点进行探索（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并不是说我是第一个发明它的人：)

2020-07-28