二叉(搜索)树前中后序遍历的递归实现的空间复杂度该如何分析?

来源: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回答

liuyubobobo

2018-10-13

对于树的遍历算法,如论是前中后序遍历,时间复杂度都是O(n)的,其中n是树中节点个数。因为每一个节点在递归的过程中,只访问了一次:)


----------


空间复杂度,通常说是O(h)的,其中h是树的最大高度。这是因为,在递归的过程中,每向下递归一层,就需要占用一定的系统栈空间。最多占用h的空间。


在这里要注意,我们说空间复杂度,通常是指完成算法所用的辅助空间的复杂度,而不用管算法前置的空间复杂度。比如在树的遍历算法中,整棵树肯定要占O(n)的空间,n是树中节点的个数,这部分空间是“平凡”的,即肯定存在的,我们不讨论他。


另外,值得一提的是,对于平衡二叉树,我们会说其空间复杂度是O(logn)的,这是因为平衡二叉树的高度h就是O(logn)级别的。但是对于一般的树,严谨起见,还是要说O(h)的。这个h可能是logn(最好情况),也可能是n(最坏情况):)


1
2
liuyubobobo
回复
Genpeng
抱歉,忘记了。我补充在原答案上了:)
2018-10-13
共2条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程