重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例:
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
提示:
0 <= 节点个数 <= 5000
题目分析
众所周知:
- 先序遍历的首先遍历的是根节点,所以先序遍历结果的第一个值是根节点的值
- 中序遍历先遍历的是根节点的左子树,接着是根节点的值,再是根节点的右子树,所以中序遍历根节点的值左边的是根节点的左子树中序遍历结果,右边是右子树的中序遍历结果
根据上面的两个基本知识,这道题就基本差不多了:
1. 根据[3,9,20,15,7],可以知道这棵树的根节点是3
2. 根据[9,3,15,20,7],找到根节点的位置,可以知道左子树为[9],右子树为[15,20,7]
3. 序列[9]回到1,构建出节点3的左子树,序列[15,20,7]回到1,构建出节点3的右子树
4. 返回结果
我的做法是遍历中序数组去寻找根节点的位置,所以时间复杂度是O(N*LogN),看了题解,发现大牛们使用HashMap<TreeNode,Integer>来存放数组,实现了O(1)的寻找节点,所以他们做法的时间复杂度是O(N),但是算法的思路适合我上面的一样的,我就不贴他们的代码了。下面是我的代码:
private int[] preorder;
private int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0)
return null;
this.preorder = preorder;
this.inorder = inorder;
return buildTree(0, preorder.length - 1, 0, preorder.length - 1);
}
private TreeNode buildTree(int headPreOrder, int tailPreOrder, int headInOrder, int tailInOrder) {
if (headPreOrder < 0 || tailPreOrder >= preorder.length || headPreOrder > tailPreOrder)
return null;
if (headInOrder < 0 || tailInOrder >= preorder.length || headInOrder > tailInOrder)
return null;
if (headPreOrder == tailPreOrder)
return new TreeNode(preorder[headPreOrder]);
// 先序遍历里的第一个就是头结点
TreeNode root = new TreeNode(preorder[headPreOrder]);
// 找出头结点在中序遍历的位置,从而得到左子树和右子树
int headInInorderIndex = 0;
for (int i = headInOrder; i <= tailInOrder; i++) {
if (preorder[headPreOrder] == inorder[i]) {
headInInorderIndex = i;
break;
}
}
// 左子树里的节点的个数
int leftSize = headInInorderIndex - headInOrder;
root.left = buildTree(headPreOrder + 1, headPreOrder + leftSize, headInOrder, headInInorderIndex - 1);
root.right = buildTree(headPreOrder + leftSize + 1, tailPreOrder, headInInorderIndex + 1, tailInOrder);
return root;
}
网友评论