企业官网建设流程全解析

题目

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

示例 1:

输入:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出:[3,9,20,null,null,15,7]

示例 2:

输入:preorder = [-1], inorder = [-1]输出:[-1]

提示:

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

题解

/** * 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 { HashMap<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { // 记录中序每个值对应的下标 for(int i = 0; i < inorder.length; i++){ map.put(inorder[i], i); } return build(preorder, 0, preorder.length-1, 0, inorder.length-1); } /** * preL,preR：前序区间 [preL, preR] * inL,inR：中序区间 [inL, inR] */ TreeNode build(int[] preorder, int preL, int preR, int inL, int inR){ if(preL > preR) return null; // 根节点是前序最左边 int rootVal = preorder[preL]; TreeNode root = new TreeNode(rootVal); // 根在中序中的位置 int rootIdx = map.get(rootVal); // 左子树节点个数 int leftSize = rootIdx - inL; // 构建左子树：前序[preL+1, preL+leftSize]，中序[inL, rootIdx-1] root.left = build(preorder, preL+1, preL+leftSize, inL, rootIdx-1); // 构建右子树：前序[preL+leftSize+1, preR]，中序[rootIdx+1, inR] root.right = build(preorder, preL+leftSize+1, preR, rootIdx+1, inR); return root; } }

思路

1. 拿前序第一个值作为根；
2. 在中序找到根的下标，左边全部是左子树，右边全部是右子树；
3. 算出左子树节点数量，切分前序数组的左右部分；
4. 递归构建左、右子树。