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

inorderStart 和 inorderEnd 是中序遍历序列下标索引。

java 递归实现

class Solution {private HashMap<Integer, Integer> inorderIndexMap;private int preorderIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {inorderIndexMap = new HashMap<>();preorderIndex = 0;for(int i = 0; i < inorder.length; i++) {inorderIndexMap.put(inorder[i], i); //存放中序遍历值和索引的映射}return Helper(preorder, 0, inorder.length - 1);}private TreeNode Helper(int[] preorder, int inorderStart, int inorderEnd) {if(inorderStart > inorderEnd) return null;//首先从先根遍历序列中获取当前节点值int rootValue = preorder[preorderIndex++];TreeNode root = new TreeNode(rootValue);//在中根遍历中找到根节点的位置int inorderIndex = inorderIndexMap.get(rootValue);//构建左子树root.left = Helper(preorder, inorderStart, inorderIndex - 1);//构建右子树root.right = Helper(preorder, inorderIndex + 1, inorderEnd);return root;}
}