友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1] 输出: [-1]
提示:
-
1 <= preorder.length <= 3000 -
inorder.length == preorder.length -
-3000 <= preorder[i], inorder[i] <= 3000 -
preorder和inorder均 无重复 元素 -
inorder均出现在preorder -
preorder保证 为二叉树的前序遍历序列 -
inorder保证 为二叉树的中序遍历序列
思路分析
-
一刷
-
二刷
-
二刷
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
/**
* 自我实现，感觉比 https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution[My Accepted Java Solution - LeetCode Discuss] 简单。
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-25 11:27
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
return buildTree(preorder, inorder, 0, 0, preorder.length);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int pre, int in, int size) {
int val = preorder[pre];
TreeNode root = new TreeNode(val);
int leftSize = 0;
int i = in;
for (; i < size + in; i++) {
if (inorder[i] == val) {
break;
}
leftSize++;
}
if (leftSize > 0) {
root.left = buildTree(preorder, inorder, pre + 1, in, leftSize);
}
int rightSize = size - leftSize - 1;
if (rightSize > 0) {
root.right = buildTree(preorder, inorder, pre + leftSize + 1, i + 1, rightSize);
}
return root;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-25 11:27
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, 0, 0, preorder.length);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int pre, int in, int length) {
if (length <= 0) {
return null;
}
int val = preorder[pre];
TreeNode root = new TreeNode(val);
int inIdx = in;
while (inIdx < in + length) {
if (inorder[inIdx] == val) {
break;
}
inIdx++;
}
root.left = buildTree(preorder, inorder, pre + 1, in, inIdx - in);
root.right = buildTree(preorder, inorder, pre + 1 + (inIdx - in), inIdx + 1, length - 1 - (inIdx - in));
return root;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-11 21:37:06
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
return dfs(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode dfs(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int value = preorder[preStart];
TreeNode root = new TreeNode(value);
int index = inStart;
for (; index <= inEnd; index++) {
if (inorder[index] == value) {
break;
}
}
root.left = dfs(preorder, preStart + 1, preStart + (index - inStart),
inorder, inStart, index - 1);
root.right = dfs(preorder, preStart + (index - inStart) + 1, preEnd,
inorder, index + 1, inEnd);
return root;
}
思考题
迭代构建如何实现？ 参考： 105. 从前序与中序遍历序列构造二叉树。