含循环的递归算法时间复杂度分析——LeetCode二叉树构建问题

算法代码 #

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0,0, inorder.length - 1, preorder, inorder);
    }
    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder){
        if(preStart > preorder.length - 1 || inStart > inEnd){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preStart]);

        int inIndex = 0;
        for(int i = 0; i <= inEnd; i++){
            if(root.val == inorder[i]){
                inIndex = i;
            }
        }           

        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);

        return root;
    }
}

问题描述 #

以下是LeetCode中基于前序遍历数组preorder和中序遍历数组inorder构建二叉树的Java递归算法，请问该含循环的递归算法的时间复杂度如何计算？我认为当输入数组长度为N时，时间复杂度为O(N²)，因为递归调用中包含循环，该结论是否正确？请确认该算法的时间复杂度。

解答 #

你的结论是正确的，该算法的时间复杂度确实为O(N²)，具体分析如下：

• 递归调用次数：整个算法会为每个节点执行一次helper方法，总共有N次递归调用（N为节点总数）。
• 每次递归的循环开销：在每个helper调用中，都需要遍历当前子树对应的中序数组区间，找到根节点的索引。最坏情况下（比如二叉树退化为单链结构，所有节点只有左子树或只有右子树），每次循环的遍历长度依次为N、N-1、N-2...1，总遍历次数为N*(N+1)/2，属于O(N²)的量级。
• 其余操作（创建节点、递归参数传递等）均为常数时间O(1)，不会影响整体时间复杂度。

如果想要将时间复杂度优化到O(N)，可以提前用哈希表存储中序数组中元素与对应索引的映射，这样每次查找根节点位置的操作就能从O(k)（k为当前区间长度）降至O(1)，整体复杂度即可优化为线性级别。

内容的提问来源于stack exchange，提问作者dhhhhhhh