day46（12.27）——leetcode面试经典150

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

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

题目：

题解：

/** * 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 { //创建Map映射 public int[] preorder; public Map<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { //为全局变量preorder赋值 this.preorder = preorder; for(int i=0;i<inorder.length;i++) { map.put(inorder[i], i); } return recur(0,0,inorder.length-1); } TreeNode recur(int root, int left, int right) { if(left > right){ return null; } //创建结点 TreeNode node = new TreeNode(preorder[root]); //进行获取中间结点 int i = map.get(preorder[root]); node.left = recur(root+1, left, i-1); node.right = recur(root+i-left+1, i+1, right); return node; } }