查找二进制树的最大深度深度的递归机制非常简单，但是如果没有递归，我们怎样才能有效地执行它，因为我有一个大树，我宁愿避免这种递归。
//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<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 不是我声称我是第一个发明它:)
此变体使用两个堆栈，一个用于探索其他节点（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 不是我声称我是第一个发明它:)
您描述的递归方法本质上是二叉树上的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<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;
}
如果您可以在每个节点维护左右值，则可以完成。
http://leetcode.com/2010/04/maximum-height-of-binary-tree.html。
可能重复： 以递归方式检索二叉树节点的深度
另一种方法是使用 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;
}
使用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;
}
这是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;
}
请注意，您还可以返回minHeight。 为了使它DFS只是用Stack替换Queue。