/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//前序数组的顺序 根节点 左子树 右子树
//中序数组的顺序 左子树 根节点 右子树
//1. 将中序遍历的数组 遍历添加到Map中，key = inorder[i] value = i
//2. 根据前序遍历获取根节点
//3. 从map中获取根节点的索引 rootIndex
//4. 计算
// 在前序数组中
// 左子树节点数 leftNodes = rootIndex - inorderStart
// 右子树节点数 rightNodes = inorderEnd - rootIndex
// 左子树 开始索引 preorderStart+1 结束索引为 preorderStart+leftNodes
// 右子树 开始索引 preorderEnd - rightNodes + 1 结束索引为 preorderEnd
//在中序数组中
//左子树 开始索引 inorderStart 结束索引 rootIndex - 1
//右子树 开始索引 rootIndex+1 结束索引 inorderEnd
//难点 计算前序数组的各个索引。
// end - start + 1 = node
// end = start + node - 1
// start = end - node + 1
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
int length = preorder.length;
//将中序数组遍历 添加到Map中
for (int i = 0; i < length; i++) {
indexMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
//判断
if (preorderStart > preorderEnd) {
return null;
}
//前序遍历的第一个节点时根节点
int rootVal = preorder[preorderStart];
TreeNode root = new TreeNode(rootVal);
//开始和结束相同 则返回根节点
//递归终止的条件
if (preorderStart == preorderEnd) {
return root;
} else {
//获取根节点的索引
int rootIndex = indexMap.get(rootVal);
//根节点索引-开始索引 = 左子树节点个数
//结束索引 - 根节点索引 = 右子树个数
int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
}
}