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

Question

波波老师：
您好，我的问题如下：

对于二叉（搜索）树前中后序遍历的递归实现，它的时间和空间复杂度该如何分析？

例如：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);
    }
}

该如何分析这段代码的时间和空间复杂度呢？
麻烦老师了。

Answer 1

liuyubobobo 2018-10-13 10:07:27

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

----------

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

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

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

• 提问者 Genpeng #1

  老师，空间复杂度也是O(n)吗？

• liuyubobobo 回复 提问者 Genpeng #2

  抱歉，忘记了。我补充在原答案上了：）