时间戳

首页 > 解决方案 > 为什么在这个树遍历中只有 log(N) 递归调用？

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

问题描述

下面的代码是这个问题的解决方案：“给定一棵二叉树，设计一个算法来创建每个深度的所有节点的链表（例如，如果你有一个深度为 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.leftand root.right，所以不应该有 O(N) 递归调用吗？树中的每个节点一个？

“该解决方案使用 O(log N) 递归调用（在平衡树中），每个调用都会向堆栈添加一个新级别”

对不起，我真的很困惑，不胜感激，谢谢！

标签： javarecursionarraylistlinked-listbinary-tree

解决方案

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

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

推荐阅读