存储路径的空间复杂度是多少,即。数组中从根到特定叶子的二叉树节点?
基本上,我正在寻找以下算法的空间复杂度:
public void printPath () {
doPrint(root, new ArrayList<TreeNode>());
}
private void doPrint(TreeNode node, List<TreeNode> path) {
if (node == null) return;
path.add(node);
if (node.left == null && node.right == null) {
System.out.println("Path from root: " + root.item + " to leaf: " + node.item + " - ");
for (TreeNode treeNode : path) {
System.out.print(treeNode.item + " ");
}
System.out.println();
}
doPrint(node.left , path);
doPrint(node.right, path);
path.remove(path.size() - 1);
}
最佳答案
如果您的树是平衡的,那么它将是 O(log n)
。这是因为平衡二叉树在每个后续级别上的节点数量都是原来的两倍,因此如果将树中的节点数量加倍,它只会增加一个附加层。
该路径仅包含当前节点的父节点,因此您最终不会包含整棵树。
如果您的树完全不平衡(即每个节点只有一个或更少的 child ),那么您最终将在列表中保留整个树,因为您必须遍历树中的每个节点才能到达单个叶子。在这种情况下,它将是 O(n)
。
关于java - 打印从根到叶的所有路径的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28304050/