
luckydog
V1
2022/03/17阅读:40主题:默认主题
Code_105
先序和中序构造二叉树
tips : 先序,后序不能确定二叉树。
思路
先序 : 根--左--右
中序:左--根--右
在先序中找根分割中序为左右子树,再去找左右子树的跟再分割,可以递归实现。
实现
建树函数返回所见树的根节点,所需参数:先序数组,中序数组,两个数组的left,right索引。 HashMap存储中序的值和对应索引,方便分割中序数组。 preLeft = 左子树的inRight = HashMap.get(preOrder[preLeft]) - 1 左子树的inLeft = 0 左子树的preLeft = preLeft + 1 左子树的PreRight = HashMap.get(preOrder[preLeft]) 右子树 inLeft = HashMap.get(preOrder[preLeft]) + 1 右子树的inRight = n - 1 右子树的preLeft = HashMap.get(preOrder[preLeft]) + 1 右子树的PreRight = n - 1
HashMap<Integer, Integer> hashMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
hashMap = new HashMap<>();
for (int i = 0; i < preorder.length; i++) {
hashMap.put(inorder[i], i);
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
public TreeNode myBuildTree(int[] preorder,
int[] inorder, int leftPreorder,
int rightPreorder, int leftInorder, int rightInorder) {
if (leftPreorder > rightPreorder) {
return null;
}
int preOrderRoot = leftPreorder;
int inOrderRoot = hashMap.get(preorder[preOrderRoot]);
TreeNode node = new TreeNode(preorder[preOrderRoot]);
int leftTreeSize = inOrderRoot - leftInorder;
node.left = myBuildTree(preorder, inorder,
leftPreorder + 1,
leftPreorder + leftTreeSize,
leftInorder,
inOrderRoot - 1);
node.right = myBuildTree(preorder, inorder,
leftPreorder + leftTreeSize + 1,
rightPreorder,
inOrderRoot + 1,
rightInorder);
return node;
}
作者介绍

luckydog
V1