二叉树O（n）的InOrder树遍历的时间复杂度？

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); } } 

资料来源：Wiki Tree Traversal

时间复杂度是O（n）吗？ 如果使用递归完成，时间复杂度是否会相同？

新问题：如果我使用上面的代码从TreeA中找到某个节点来创建另一个树TreeB，它将拥有与TreeA一样多的节点，那么创建TreeB的复杂性将是O（n ^ 2），因为它是n个节点和每个节点都会使用上面的代码，即O（n）？

Answer 1

由于二叉树的遍历 （与搜索和大多数其他树操作相反）需要处理所有树节点，因此任何遍历算法的最小复杂度为O（n），即线性地表示树中的节点数。 这是一个不可改变的事实，除非有人建造量子计算机或其他东西，否则在一般情况下不会改变……

至于递归，唯一的区别是递归方法调用通过将调用帧推送到JVM堆栈来隐式地构建堆栈，而您的示例代码显式构建堆栈。 我宁愿不推测两者之间的任何性能差异 – 您应该为每个特定用例场景分析和基准测试。