递归(三)从前序与中序遍历序列构造二叉树

对应 LeetCode 105 从前序与中序遍历序列构造二叉树

问题描述

给定两个整数数组 \(pre\) 和 \(in\),其中 \(pre\) 是二叉树的先序遍历结果,而 \(in\) 是改二叉树的中序遍历结果,请通过 \(pre\) 和 \(in\) 来重新构建该二叉树并返回其对应的根节点

提示:

  • 该二叉树中不存在重复元素

  • \(0 \leq\) 节点数 \(\leq5000\)

解决思路

  • 递归

    同样的,在处理树的问题时,优先考虑使用递归的方式进行处理

    在这里,由于给定了先序遍历和中序遍历,在每次递归时都能够确定每个根节点的位置,因此该算法在理论上是可行的

    只需注意每次处理的位置即可,递归的终止条件为待处理的数据列表的长度为 \(0\)

  • 递归 + HashMap

    可以通过引入 HashMap 来提高搜索根节点的位置,但是这种方式只能处理不包含重复元素的二叉树

实现

  • 递归

    class Solution {
        int[] pre, in;
    
        public TreeNode buildTree(int[] _pre, int[] _in) {
            pre = _pre;in = _in;
            int n = pre.length;
    
            return recur(0, n - 1, 0, n - 1);
        }
    
        TreeNode recur(int preLo, int preHi, int inLo, int inHi) {
            if (preLo > preHi || inLo > inHi) 
                return null;
    
            int e = pre[preLo], idx = -1;
            // 这里通过查找和当前先序遍历访问的节点记性比较,相同则为根节点
            for (int i = inLo; i <= inHi; ++i) {
                if (in[i] == e) {
                    idx = i;
                    break;
                }
            }
    
            if (idx < 0) throw new IllegalArgumentException();
    
            TreeNode root = new TreeNode();
            root.val = e;
            // 注意这里左右区间的范围
            root.left = recur(preLo + 1, preHi, inLo, idx - 1);
            root.right = recur(preLo + idx - inLo + 1, preHi, idx + 1, inHi);
    
            return root;
        }
    }
    

    复杂度分析:

    • 时间复杂度:递归处理需要 \(O(n)\) 的时间复杂度,根节点的查找操作需要 \(O(n)\) 的时间复杂度,整体时间复杂度为 \(O(n^2)\)

    • 空间复杂度:忽略由于递归带来的开销,总体空间复杂度为 \(O(1)\)

  • 递归 + HashMap

    class Solution {
        int[] pre, in;
        final Map<Integer, Integer> map = new HashMap<>();
    
        public TreeNode buildTree(int[] _pre, int[] _in) {
            pre = _pre;in = _in;
            int n = pre.length;
            for (int i = 0; i < n; ++i) map.put(in[i], i);
    
            return recur(0, n - 1, 0, n - 1);
        }
    
        TreeNode recur(int preLo, int preHi, int inLo, int inHi) {
            if (preLo > preHi || inLo > inHi) 
                return null;
    
            int e = pre[preLo], idx = map.get(e);
    
            TreeNode root = new TreeNode();
            root.val = e;
            root.left = recur(preLo + 1, preHi, inLo, idx - 1);
            root.right = recur(preLo + idx - inLo + 1, preHi, idx + 1, inHi);
    
            return root;
        }
    }
    

    复杂度分析:

    • 时间复杂度:递归处理需要 \(O(n)\) 的时间复杂度,HashMap 进行查找操作需要 \(O(1)\) 的时间复杂度,总体时间复杂度为 \(O(n)\)

    • 空间复杂度:存储 HashMap 需要额外的空间,空间复杂度为 \(O(1)\)

上一篇:LC-69


下一篇:分布式id生成之雪花id