Java 二叉树中序树遍历的时间复杂度O(n)？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9658700/
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
Time Complexity of InOrder Tree Traversal of Binary Tree O(n)?
提问by Dan
public void iterativePreorder(Node root) {
Stack nodes = new Stack();
nodes.push(root);
Node currentNode;
while (!nodes.isEmpty()) {
currentNode = nodes.pop();
Node right = currentNode.right();
if (right != null) {
nodes.push(right);
}
Node left = currentNode.left();
if (left != null) {
nodes.push(left);
}
System.out.println("Node data: "+currentNode.data);
}
}
Source: Wiki Tree Traversal
来源：维基树遍历
Is the time complexity going to be O(n)? And is the time complexity going to be the same if it was done using recursion?
时间复杂度是 O(n) 吗？如果使用递归完成，时间复杂度是否相同？
New Question: If I were to use to above code to find a certain node from a TreeA to create another tree TreeB which will have as much nodes as TreeA, then would the complexity of creating TreeB be O(n^2) since it is n nodes and each node would use the above code which is O(n)?
新问题：如果我使用上面的代码从 TreeA 中找到某个节点来创建另一棵树 TreeB，它的节点数与 TreeA 一样多，那么创建 TreeB 的复杂性是否为 O(n^2)，因为它是n 个节点，每个节点将使用上面的代码，即 O(n)？
采纳答案by thkala
Since the traversalof a binary tree (as opposed to the search and most other tree operations) requires that alltree nodes are processed, the minimum complexity of any traversal algorithm is O(n), i.e. linear w.r.t. the number of nodes in the tree. That is an immutable fact that is not going to change in the general case unless someone builds a quantum computer or something...
由于二叉树的遍历（与搜索和大多数其他树操作相反）需要处理所有树节点，因此任何遍历算法的最小复杂度为 O(n)，即与树中的节点数成线性关系. 这是一个不变的事实，在一般情况下不会改变，除非有人建造了量子计算机或其他东西……
As for recursion, the only difference is that recursive method calls build the stack implicitly by pushing call frames to the JVM stack, while your sample code builds a stack explicitly. I'd rather not speculate on any performance difference among the two - you should profile and benchmark both alternatives for each specific use case scenario.
至于递归，唯一的区别是递归方法调用通过将调用帧推送到 JVM 堆栈来隐式构建堆栈，而您的示例代码显式构建堆栈。我宁愿不推测两者之间的任何性能差异 - 您应该针对每个特定用例场景对两种替代方案进行概要分析和基准测试。
