二叉(搜索)树前中后序遍历的递归实现的空间复杂度该如何分析?
来源:7-7 基于二分搜索树的映射实现
Genpeng
2018-10-13
波波老师:
您好,我的问题如下:
对于二叉(搜索)树前中后序遍历的递归实现,它的时间和空间复杂度该如何分析?
例如:LeetCode 上第144号问题——二叉树的前序遍历,它的递归实现方式如下(Java):
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preorderTraversal(root, res);
return res;
}
private void preorderTraversal(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
preorderTraversal(root.left, res);
preorderTraversal(root.right, res);
}
}
该如何分析这段代码的时间和空间复杂度呢?
麻烦老师了。
写回答
1回答
-
对于树的遍历算法,如论是前中后序遍历,时间复杂度都是O(n)的,其中n是树中节点个数。因为每一个节点在递归的过程中,只访问了一次:)
----------
空间复杂度,通常说是O(h)的,其中h是树的最大高度。这是因为,在递归的过程中,每向下递归一层,就需要占用一定的系统栈空间。最多占用h的空间。
在这里要注意,我们说空间复杂度,通常是指完成算法所用的辅助空间的复杂度,而不用管算法前置的空间复杂度。比如在树的遍历算法中,整棵树肯定要占O(n)的空间,n是树中节点的个数,这部分空间是“平凡”的,即肯定存在的,我们不讨论他。
另外,值得一提的是,对于平衡二叉树,我们会说其空间复杂度是O(logn)的,这是因为平衡二叉树的高度h就是O(logn)级别的。但是对于一般的树,严谨起见,还是要说O(h)的。这个h可能是logn(最好情况),也可能是n(最坏情况):)
122018-10-13
相似问题