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

@TOC

题目描述

 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

105. 从前序与中序遍历序列构造二叉树

示例：

提示：

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

一、解题关键词

二、解题报告

1.思路分析

1. 构建树。按照树的特点
2. 两种顺序遍历 有助于确定唯一的树
3. 数据无重复 数据元素相同 只是顺序不同
4. 树一定用递归
5. 需要先确定根节点
6. 先序最开始的是根节点 so
7. 先序是 根左右 中序是左根右
8. 左右节点一定会分开讨论，但是左右节点分开构建的时候一定有差别（构建数组下标参数）

2.时间复杂度

3.代码示例

/**
 * 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 {
      private Map indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int pLen = preorder.length;
        int iLen = inorder.length;
        indexMap = new HashMap<>();

        for(int i = 0; i < pLen;i++){
            indexMap.put(inorder[i],i);
        }
        return dfs(preorder,inorder,0,pLen - 1,0,iLen - 1);
    }
    TreeNode dfs(int[] preorder, int[] inorder,int pl,int pr,int il,int ir){
        //终止程序 条件是所有元素遍历完毕
        if(pl > pr){
            return null;
        }
        TreeNode nowNode = new TreeNode(preorder[pl]);
      //pos 是根节点坐标
        int pos = indexMap.get(preorder[pl]);
        int cnt = pos - il;
      //分别设置 先序，中序长度。不要人肉递归 
        nowNode.left = dfs(preorder,inorder,pl + 1,pl + cnt,il,pos - 1);
        nowNode.right = dfs(preorder,inorder,pl + cnt + 1,pr,pos + 1,ir);
        return nowNode;
    }
}

4.知识点

递归只需要总结当前层的处理逻辑

---

三、总结