如何迭代地找到BST的高度？

public void HeightIterative() { int counter = 0; int counter2 = 0; TreeNode current=root; if(current != null) { while(current.LeftNode!=null) { counter++; current = current.LeftNode; } while(current.RightNode!=null) { counter2++; current = current.RightNode; } } int res = 1+Math.Max(counter, counter2); Console.WriteLine("The Height Of Tree Is: "+res); } 

我写了迭代方法，来计算树的高度。 但在某些情况下它不能正常工作。 如案例：10 1 2 3 4 5 18 17 16 15 14 13问题是什么。 根据这个序列树的高度是6，我的代码显示5。

Answer 1

您正在使用两个循环，但每个循环仅调查节点的一个，但树中的每个节点都有两个侧面，您应该调查它们。 你可以通过递归调用来完成它。

 private int GetLen(TreeNode node) { var result = 0; if(node != null) { result = Math.Max(GetLen(node.LeftNode), GetLen(node.RightNode)) + 1; } return result; } public void HeightIterative() { int res = GetLen(root); Console.WriteLine("The Height Of Tree Is: "+res); } 

迭代版本：

 private class NodeInfo { public NodeInfo(TreeNode node, int len) { Node = node; Len = len; } public TreeNode Node {get; private set;} public int Len {get; private set;} } public void HeightIterative() { int maxLen = 0; var queue = new Queue(); queue.Enqueue(new NodeInfo(root, 1)); while (queue.Count > 0) { var item = queue.Dequeue(); var current = item.Node; var currentLen = item.Len; if (current.LeftNode != null) { queue.Enqueue(new NodeInfo(current.LeftNode, currentLen + 1)); } if (current.RightNode != null) { queue.Enqueue(new NodeInfo(current.RightNode, currentLen + 1)); } if (currentLen > maxLen) { maxLen = currentLen; } } Console.WriteLine("The Height Of Tree Is: " + maxLen); } 

Answer 2

除了用于存储节点的队列之外，有一种方法不需要任何额外的空间。

1. 添加当前元素的子节点并记住队列的大小。
2. 让每个出队呼叫递减计数器
3. 当计数器达到零时，表示我们已完成当前级别。
4. 重复和计数计数器达到零的次数 – 这是树的深度/高度

代码是这样的：

 public int treeDepth(Node root){ int height = 0; int counterNodesInLevel = 1; if(root!=null) { Queue queue=new Queue() queue.enqueue(root); while (!queue.isEmpty()){ Node current = queue.dequeue(); counterNodesInLevel -= 1; if(current.left!=null){ queue.enqueue(current.left) } if(current.right!=null){ queue.enqueue(current.right) } if (counterNodesInLevel == 0){ height += 1; counterNodesInLevel = queue.Size(); } } } return height; } 

时间复杂度为O（N），空间复杂度为O（N）

Answer 3

问题：

您在第一个循环中找到最左侧节点的深度，在第二个循环中找到最右侧节点的深度，并且从不询问涉及向左和向右下行的任何节点。

一个办法：

有一个循环向下钻取左边的节点，但是将每个右边的节点添加到“跳过”队列中。 当您用完左侧节点时，从队列中弹出一个节点并继续，直到队列变空。 您需要存储放入该节点的队列中每个节点的高度。