为什么在这个树遍历中只有 log(N) 次递归调用？

Question

下面的代码就是这个问题的解决方案："Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked list".

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) 次递归调用吗？树中的每个节点一个？

"The solution uses O(log N) recursive calls (in a balanced tree), each of which adds a new level to the stack"

抱歉，我真的很困惑，希望得到解释谢谢！

Answer 1

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

你说的是函数调用的次数是N。但是递归的最大深度（嵌套函数调用）是log N。

为什么在这个树遍历中只有 log(N) 次递归调用？

Why are there only log(N) recursive calls made in this tree traversal?

java

recursion

binary-tree

linked-list

arraylist