二叉（搜索）树前中后序遍历的递归实现的空间复杂度该如何分析？
来源：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
相似问题