Repository navigation
Expand file tree
/
Copy path_07_buildTree.java
More file actions
103 lines (92 loc) · 3.26 KB
/
Copy path_07_buildTree.java
File metadata and controls
103 lines (92 loc) · 3.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package pp.arithmetic.offer;
import pp.arithmetic.Util;
import pp.arithmetic.model.TreeNode;
/**
* Created by wangpeng on 2020-08-04.
*
* 剑指 Offer 07. 重建二叉树
*
* 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
*
*
*
* 例如，给出
*
* 前序遍历 preorder = [3,9,20,15,7]
* 中序遍历 inorder = [9,3,15,20,7]
* 返回如下的二叉树：
*
* 3
* / \
* 9 20
* / \
* 15 7
*
*
* 限制：
*
* 0 <= 节点个数 <= 5000
*
*
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _07_buildTree {
public static void main(String[] args) {
_07_buildTree buildTree = new _07_buildTree();
int[] preorder = {3, 9, 20, 15, 7};
int[] inorder = {9,3,15,20,7};
TreeNode treeNode = buildTree.buildTree(preorder, inorder);
Util.printTree(treeNode);
}
/**
* 解题思路：
* 1、知道前序遍历，首位就是根节点
* 2、由于不存在重复数字，根据根节点找到中序遍历的位置I，I前就是左子树的中序，I后就是右子树的中序
* 3、在前序数组中，根据左右子树中序的长度，能找到左右子树对应的前序遍历数组
* 4、循环1-3，得到左右子树的对应的前序&中序数组，最终得到构建的树
*
* 优化建议：得到左右子树对应的数组的时候，有两种方案:
* 一、拷贝新数组
* 二、原数组上理由index指针获取结果（性能和效率都更高）
*
* 本题解基于方案二
*
* @param preorder
* @param inorder
* @return
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
return dfs(preorder.length,preorder,0,inorder,0);
}
// 从前序和中序构造二叉树，前序和中序是大数组中的一段[start, start + count)
private TreeNode dfs(int count, int[] preOrder, int preStart, int[] inOrder, int inStart) {
if (count <= 0) return null;
int rootValue = preOrder[preStart];
TreeNode root = new TreeNode(rootValue);
// 从inorder中找到root值，(inorder)左边就是左子树，(inorder)右边就是右子树
// 然后在preorder中，数出与inorder中相同的个数即可
int pos = inStart + count - 1;
for (; pos >= inStart; --pos) {
if (inOrder[pos] == rootValue) {
break;
}
}
int leftCount = pos - inStart;
int rightCount = inStart + count - pos - 1;
if (leftCount > 0) {
int leftInStart = inStart;
int leftPreStart = preStart + 1;
root.left = dfs(leftCount, preOrder, leftPreStart, inOrder, leftInStart);
}
if (rightCount > 0) {
int rightInStart = pos + 1;
int rightPreStart = preStart + 1 + leftCount;
root.right = dfs(rightCount, preOrder, rightPreStart, inOrder, rightInStart);
}
return root;
}
}