LeetCode 图解 | 105.用前序和中序遍历序列构建二叉树

今天分享的题目来源于 LeetCode 第 105 号问题：用前序和中序遍历序列构建二叉树。

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [28，16，13，22，30，29，43]
中序遍历 inorder = [13，16，22，28，29，30，43]

返回如下的二叉树：

         28
       /    
     16     30
    /      /  
   13  22  29  43

题目解析

先来了解一下什么是前序遍历、中序遍历、后序遍历。

前序遍历：遍历顺序为 父（根）节点 -> 左子节点 -> 右子节点

中序遍历：遍历顺序为 左子节点 -> 父（根）节点 -> 右子节点

后序遍历：遍历顺序为 左子节点 -> 右子节点 -> 父（根）节点 

再说明一个结论：前序/后序 + 中序遍历可以确定一棵唯一二叉树。

题目中给出的是 前序 + 中序 的组合，那么我们仔细观察对比一下 前序遍历 与 中序遍历。

• 前序中左起第一位 28 肯定是根结点，以此为根据找到中序中根结点的位置 rootIdx

• 中序中根结点左边就是左子树结点，右边就是右子树结点，即[左子树结点，根结点，右子树结点]，我们就可以得出左子树结点个数为 int leftLen = rootIdx - leftIdx

• 前序中结点分布应该是：[根结点，左子树结点，右子树结点]

• 根据前一步确定的左子树个数，可以确定前序中左子树结点和右子树结点的范围

如果我们要递归生成二叉树的话，下一层递归应该是：

• 左子树：root->left = buildTree(前序左子树范围，前序起始下标，前序结束下标，中序开始下标);；

• 右子树：root->right = buildTree(前序左子树范围，前序起始下标，前序结束下标，中序开始下标);。

两个注意点：

• 每一层递归都要返回当前根结点root；

• 为了避免在递归过程中线性查找，可以借助 哈希表 来储存中序的元素与下标

动画描述

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//author:程序员吴师兄
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       //借助哈希表来储存二叉树的节点，优化时间复杂度
       Map<Integer, Integer> inPos = new HashMap<>();
       for (int i = 0; i < inorder.length; ++i){
            inPos.put(inorder[i], i);
       }
       return buildTree(preorder, 0, preorder.length-1, 0, inPos);
    }

    private TreeNode buildTree( int[] pre, int preStart , int preEnd, int inStart, Map<Integer, Integer> inPos) {
    //递归停止条件
    if (preStart > preEnd) return null; 
    //前序中左起第一位肯定是根结点
    TreeNode root = new TreeNode(pre[preStart]);
    //根结点的位置直接通过中序获取
    int rootIdx = inPos.get(pre[preStart]);
    //左子树结点个数可以通过中序中根节点的位置与中序中起始位置确定
    int leftLen = rootIdx - inStart;
    //递归调用
    root.left = buildTree(pre, preStart + 1, preStart + leftLen, inStart, inPos);
    root.right = buildTree(pre, preStart + leftLen + 1, preEnd, rootIdx + 1, inPos);
    return root;
  }
}

复杂度分析

• 时间复杂度：O(n) 。 

• 空间复杂度：O(n)。借助哈希表这种数据结构，需要额外的存储空间，因此空间复杂度为 O(n)。

知识点

二叉树、递归