二叉树O(n)的InOrder树遍历的时间复杂度？

Question

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堆栈来隐式地构建堆栈,而示例代码显式地构建堆栈.我宁愿不推测两者之间的任何性能差异 - 您应该为每个特定用例场景分析和基准测试.