"最大二叉树深度"的递归方法(Java)的时间复杂度是多少？

Question

这个问题取自LeetCode的"Binary Tree of Binary Tree":

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

嗯,递归方法很简单:

public int maxDepth (TreeNode root) {  
    if(root == null)  
        return 0;  
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;  
}  

我只是无法弄清楚这个解决方案的时间复杂性.有人说是的O(n).是不是maxDepth(root.left)同时maxDepth(root.right)计算,这会使时间复杂化O(lg(n))？

Answer 1

maxDepth(root.left)和maxDepth(root.right)只有在并行运行时才能同时计算,如果是,则复杂性取决于可并行运行的可用处理器数量.也就是说,您的Java代码并没有并行运行,因为它们都在同一个线程上运行.

假设顺序执行,maxDepth必须遍历整个树,因为它不知道某个路径是否可以导致最大深度,直到它到达结束该路径的叶子.因此,时间复杂度为O(n).