一、题目描述
二、思路分析
2.1 分析
首先前序遍历的遍历顺序是根节点 -> 左节点 -> 右节点,而中序遍历的遍历顺序是左节点 -> 根节点 -> 右节点。我们可以从二叉树的前序遍历确定根节点的位置,进而在中序遍历中根据根节点划分左右子树范围。
2.2 图解
三、题解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
List<Integer> preorderList = new ArrayList<>();
List<Integer> inorderList = new ArrayList<>();
for (int i = 0; i < preorder.length; i++) {
preorderList.add(preorder[i]);
inorderList.add(inorder[i]);
}
return builder(preorderList, inorderList);
}
private TreeNode builder(List<Integer> preorderList, List<Integer> inorderList) {
if (inorderList.isEmpty()) {
return null;
}
// 取出根节点的值
int rootVal = preorderList.remove(0);
// 确定根节点的下标位置
int rootIndex = inorderList.indexOf(rootVal);
// 构建二叉树
TreeNode root = new TreeNode(rootVal);
root.left = builder(preorderList, inorderList.subList(0, rootIndex));
root.right = builder(preorderList, inorderList.subList(rootIndex + 1, inorderList.size()));
return root;
}
}