为什么在此树遍历中只进行 log(N) 递归调用

Question

以下代码是这个问题的解决方案："给定一个二叉树，设计一个算法，在每个深度创建所有节点的链表(例如，如果你有一棵深度为 D 的树，你将有 D 链表"。

void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode>>lists, int level) {
   if(root == null) return; //base case
   LinkedList<TreeNode> list = null;
   if (lists.size()==level){ //Level not contained in list
      list = new LinkedList<TreeNode>();
      lists.add(list);
   } else{
     list = lists.get(level);
   }
   list.add(root);
   createLevelLinkedlist(root.left, lists, level+1);
   createLevelLinkedList(root.right, lists, level+1);
}
ArrayList<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root){
   ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
   createLevelLinkedlist(root, lists, 0);
   return lists;
}

根据解决方案，此代码的运行时为 O(N(，但使用 O(log N( 递归调用。为什么只有 O(log N( 递归调用？看起来在每个调用中，总是有两个新的递归调用root.left和root.right，所以不应该有O(N(递归调用吗？树中的每个节点一个？

"该解决方案使用 O(log N( 递归调用(在平衡树中(，每个递归调用都为堆栈增加了一个新级别"

对不起，我真的很困惑，希望得到解释谢谢！

Answer 1

它讨论了递归调用的深度。如果你仔细观察它，对于一个平衡的二叉树，它递归的次数与树的高度相同，即对数N。当一个函数调用自身时，将其视为具有 2 个链接的链，并且没有单个链可以拥有超过日志 N 个链接。

你说的是函数调用的数量，即 N。但是递归的最大深度(嵌套函数调用(是log N。