题目给定两个整数数组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 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列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 { HashMapInteger, 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; // 构建左子树前序[preL1, preLleftSize]中序[inL, rootIdx-1] root.left build(preorder, preL1, preLleftSize, inL, rootIdx-1); // 构建右子树前序[preLleftSize1, preR]中序[rootIdx1, inR] root.right build(preorder, preLleftSize1, preR, rootIdx1, inR); return root; } }思路拿前序第一个值作为根在中序找到根的下标左边全部是左子树右边全部是右子树算出左子树节点数量切分前序数组的左右部分递归构建左、右子树。
