求不递归二叉树的最大深度

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

该变体使用两个堆栈，一个用于要探索的额外节点(wq)，另一个始终包含根节点的当前路径(path)。当我们在两个堆栈的顶部看到相同的节点时，这意味着我们已经探索了它下面的所有内容，并且可以弹出它。现在是更新树的深度的时候了。在随机或平衡树上，附加空间应该是O(log )，在最坏的情况下，当然是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，而不是说我是第一个发明它的:)

Answer 2

您所描述的递归方法本质上是二叉树上的DFS。如果您愿意，可以迭代地实现这一点，方法是存储一个显式的节点堆栈，并跟踪遇到的最大深度。

希望这能有所帮助！

Answer 3

我编写了如下逻辑，以求最大和最小深度，这不涉及递归，而且不增加空间复杂性。

// Find the maximum depth in the tree without using recursion
private static int maxDepthNoRecursion(TreeNode root) {
    return Math.max(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
}

// Find the minimum depth in the tree without using recursion
private static int minDepthNoRecursion(TreeNode root) {
    return Math.min(maxDepthNoRecursion(root, true), maxDepthNoRecursion(root, false)); 
}

private static int maxDepthNoRecursion(TreeNode root, boolean left) {
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    int depth = 0;
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (left && node.left != null) stack.add(node.left);
        // Add the right node only if the left node is empty to find max depth
        if (left && node.left == null && node.right != null) stack.add(node.right); 
        if (!left && node.right != null) stack.add(node.right);
        // Add the left node only if the right node is empty to find max depth
        if (!left && node.right == null && node.left != null) stack.add(node.left);
        depth++;
    }
    return depth;
}