在没有递归的情况下查找二叉树的最大深度
查找二进制树的最大深度深度的递归机制非常简单，但是如果没有递归，我们怎样才能有效地执行它，因为我有一个大树，我宁愿避免这种递归。
//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的答案。
此变体使用两个堆栈，一个用于探索其他节点（ wq ），另一个总是包含来自根（ path ）的当前路径。 当我们在两个堆栈的顶部看到相同的节点时，这意味着我们已经探索了它下面的所有内容并且可以弹出它。 这也是更新树深度的时候。 在随机或平衡树上，额外的空间应该是O（log n），当然最坏的情况是O（n）。
static int maxDepth (Node r) { int depth = 0; Stack wq = new Stack<>(); Stack 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不是我声称我是第一个发明它:)
您描述的递归方法本质上是二叉树上的DFS。 如果您希望通过存储显式堆栈节点并跟踪遇到的最大深度，则可以迭代地实现此操作。
希望这可以帮助！
我编写了以下逻辑来查找最大和最小深度，这不涉及递归并且不增加空间复杂度。
// 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 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; }
如果您可以在每个节点维护左右值，则可以完成。
http://leetcode.com/2010/04/maximum-height-of-binary-tree.html 。
可能重复： 非递归地检索二叉树节点的深度
另一种方法是使用Level order traversal ，其中树Level order traversal于树的级别数。 （它只能用于计算树的最小高度。）
public int maxDepth(TreeNode root) { if (root == null) return 0; LinkedList arr = new LinkedList (); // queue for current level LinkedList tmp = new LinkedList (); // queue for next level arr.add(root); int res = 0; // result TreeNode node; // tmp node while (true) { while (!arr.isEmpty()) { node = arr.poll(); if (node.left != null) tmp.add(node.left); if (node.right != null) tmp.add(node.right); } res++; if (tmp.isEmpty()) break; arr = tmp; tmp = new LinkedList (); } return res; }
使用Array存储节点层，每次都找到一个新层。 深度加一。
public int maxDepth2(TreeNode root){ if(root == null){ return 0; } int depth = 0; ArrayList oneLayer = new ArrayList (); oneLayer.add(root); while(!oneLayer.isEmpty()){ ArrayList newLayer = new ArrayList (); for(TreeNode node:oneLayer){ if(node.right!=null){ newLayer.add(node.right); } if(node.left!=null){ newLayer.add(node.left); } } oneLayer = newLayer; depth++; } return depth; }
这是BFS解决方案：
private class NodeHeight { public Node node; public int height; public NodeHeight(Node n, int height) { node = n; this.height = height; } } public int GetHeightBfs(Node root) { if(root == null) return 0; else return GetHeightBfs(new NodeHeight(root, 1)) } private int GetHeightBfs(NodeHeight root) { int maxHeight = int.Min; int minHeight = int.Max; var q = new Queue(); q.Enqueue(root); while(q.length > 0) { var nodeHeight = q.Dequeue(); var node = nodeHeight.node; int height = nodeHeight.height; if(node.left == null && node.right == null) { maxHeight = Math.max(maxHeight, height); minHeight = Math.min(minHeight, height); } if(node.left != null) q.Enqueue(new NodeHeight(node.left, height + 1); if(node.right != null) q.Enqueue(new NodeHeight(node.right, height + 1); } return maxHeight; }
请注意，您还可以返回minHeight。 为了使它DFS只是用Stack替换Queue。