友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
思路分析
-
一刷
-
二刷
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;
}
思考题
迭代构建如何实现？ 参考： 105. 从前序与中序遍历序列构造二叉树。