Java 不用递归求二叉树的最大深度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19886297/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding max depth of binary tree without recursion
提问by Hemant
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: I am looking for answers in Java.
PS：我正在寻找 Java 的答案。
采纳答案by chill
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.
此变体使用两个堆栈，一个用于要探索的附加节点 ( 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;
}
(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.htmlnot that I claim I was the first to invent it :)
（无耻的插件：几周前我有一个使用双栈进行非递归遍历的想法，在这里检查 C++ 代码http://momchil-velikov.blogspot.com/2013/10/non-recursive-tree- traversal.html并不是我声称我是第一个发明它的人 :)
回答by Prasad
If you can maintain left and right values at each node, it can be done.
如果你能在每个节点保持左右值，就可以做到。
http://leetcode.com/2010/04/maximum-height-of-binary-tree.html.
http://leetcode.com/2010/04/maximum-height-of-binary-tree.html。
Possible duplicate: Retrieving a Binary-Tree node's depth non-recursively
可能重复： 以非递归方式检索二叉树节点的深度
回答by templatetypedef
The recursive approach you've described is essentially a DFS over the binary tree. You can implement this iteratively if you'd like by storing an explicit stack of nodes and keeping track of the maximum depth encountered.
您描述的递归方法本质上是二叉树上的 DFS。如果您愿意，可以通过存储显式节点堆栈并跟踪遇到的最大深度来迭代地实现这一点。
Hope this helps!
希望这可以帮助！
回答by Hemant
I have written following logic to do find max and min depth which doesn't involve recursion and without increasing the space complexity.
我编写了以下逻辑来查找不涉及递归且不增加空间复杂度的最大和最小深度。
// 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;
}
回答by vancexu
Another way is to use Level order traversal, where tree height is equal to the number of level of a tree. (It can only be use to calulate the minimal height of a tree.)
另一种方法是使用Level order traversal，其中树高等于树的级别数。（它只能用于计算树的最小高度。）
public int maxDepth(TreeNode root) {
if (root == null) return 0;
LinkedList<TreeNode> arr = new LinkedList<TreeNode>(); // queue for current level
LinkedList<TreeNode> tmp = new LinkedList<TreeNode>(); // 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<TreeNode>();
}
return res;
}
回答by Jerry Z.
Using a Array to store a layer of nodes, each time find a new layer. the depth plus one.
用一个Array来存储一层节点，每次找一个新的层。深度加一。
public int maxDepth2(TreeNode root){
if(root == null){
return 0;
}
int depth = 0;
ArrayList<TreeNode> oneLayer = new ArrayList<TreeNode>();
oneLayer.add(root);
while(!oneLayer.isEmpty()){
ArrayList<TreeNode> newLayer = new ArrayList<TreeNode>();
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;
}
回答by Yusuf Bhagat
Here is a BFS solution:
这是一个 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<Node>();
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;
}
Note that you can also return minHeight. To make it DFS just replace Queue with Stack.
请注意，您还可以返回 minHeight。要使其成为 DFS，只需将 Queue 替换为 Stack。
