Skip to content

Commit a2c46d6

Browse files
yanglbmeyanglbme
committed
feat: add solutions to leetcode problem: No.0105
See https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
1 parent 1367cfa commit a2c46d6

File tree

6 files changed

+165
-24
lines changed

6 files changed

+165
-24
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,7 @@
8686
1. [对称二叉树](/solution/0100-0199/0101.Symmetric%20Tree/README.md)
8787
1. [二叉树的层次遍历](/solution/0100-0199/0102.Binary%20Tree%20Level%20Order%20Traversal/README.md)
8888
1. [二叉树的最大深度](/solution/0100-0199/0104.Maximum%20Depth%20of%20Binary%20Tree/README.md)
89+
1. [从前序与中序遍历序列构造二叉树](/solution/0100-0199/0105.Construct%20Binary%20Tree%20from%20Preorder%20and%20Inorder%20Traversal/README.md)
8990
1. [二叉树的最近公共祖先](/solution/0200-0299/0235.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Search%20Tree/README.md)
9091
1. [二叉搜索树的最近公共祖先](/solution/0200-0299/0236.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree/README.md)
9192

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,7 @@ Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF
8484
1. [Symmetric Tree](/solution/0100-0199/0101.Symmetric%20Tree/README_EN.md)
8585
1. [Binary Tree Level Order Traversal](/solution/0100-0199/0102.Binary%20Tree%20Level%20Order%20Traversal/README_EN.md)
8686
1. [Maximum Depth of Binary Tree](/solution/0100-0199/0104.Maximum%20Depth%20of%20Binary%20Tree/README_EN.md)
87+
1. [Construct Binary Tree from Preorder and Inorder Traversal](/solution/0100-0199/0105.Construct%20Binary%20Tree%20from%20Preorder%20and%20Inorder%20Traversal/README_EN.md)
8788
1. [Lowest Common Ancestor of a Binary Tree](/solution/0200-0299/0236.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree/README_EN.md)
8889
1. [Lowest Common Ancestor of a Binary Search Tree](/solution/0200-0299/0235.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Search%20Tree/README_EN.md)
8990

‎solution/0100-0199/0105.Construct Binary Tree from Preorder and Inorder Traversal/README.md

Lines changed: 68 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,22 +27,88 @@
2727

2828
<!-- 这里可写通用的实现逻辑 -->
2929

30+
先遍历前序节点，对于前序的根节点，在中序节点 `[i1, i2]` 中找到根节点的位置 pos，就可以将中序节点分成：左子树 `[i1, pos - 1]`、右子树 `[pos + 1, i2]`。
31+
32+
通过左右子树的区间，可以计算出左、右子树节点的个数，假设为 m、n。然后在前序节点中，从根节点往后的 m 个节点为左子树，再往后的 n 个节点为右子树。
33+
34+
递归求解即可。
35+
36+
> 前序遍历：先遍历根节点，再遍历左右子树；中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。
37+
3038
<!-- tabs:start -->
3139

3240
### **Python3**
3341

3442
<!-- 这里可写当前语言的特殊实现逻辑 -->
3543

3644
```python
37-
45+
# Definition for a binary tree node.
46+
# class TreeNode:
47+
# def __init__(self, x):
48+
# self.val = x
49+
# self.left = None
50+
# self.right = None
51+
52+
class Solution:
53+
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
54+
def build(preorder, inorder, p1, p2, i1, i2) -> TreeNode:
55+
if p1 > p2 or i1 > i2:
56+
return None
57+
root_val = preorder[p1]
58+
pos = -1
59+
for i in range(i1, i2 + 1):
60+
if inorder[i] == root_val:
61+
pos = i
62+
break
63+
root = TreeNode(root_val)
64+
# pos==i1，说明只有右子树，左子树为空
65+
root.left = None if pos == i1 else build(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1)
66+
# pos==i2，说明只有左子树，右子树为空
67+
root.right = None if pos == i2 else build(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2)
68+
return root
69+
return build(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)
3870
```
3971

4072
### **Java**
4173

4274
<!-- 这里可写当前语言的特殊实现逻辑 -->
4375

4476
```java
45-
77+
/**
78+
* Definition for a binary tree node.
79+
* public class TreeNode {
80+
* int val;
81+
* TreeNode left;
82+
* TreeNode right;
83+
* TreeNode(int x) { val = x; }
84+
* }
85+
*/
86+
class Solution {
87+
public TreeNode buildTree(int[] preorder, int[] inorder) {
88+
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
89+
}
90+
91+
private TreeNode buildTree(int[] preorder, int[] inorder, int p1, int p2, int i1, int i2) {
92+
if (p1 > p2 || i1 > i2) {
93+
return null;
94+
}
95+
int rootVal = preorder[p1];
96+
int pos = find(inorder, rootVal, i1, i2);
97+
TreeNode root = new TreeNode(rootVal);
98+
// pos==i1，说明只有右子树，左子树为空
99+
root.left = pos == i1 ? null : buildTree(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1);
100+
// pos==i2，说明只有左子树，右子树为空
101+
root.right = pos == i2 ? null : buildTree(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2);
102+
return root;
103+
}
104+
105+
private int find(int[] order, int val, int p, int q) {
106+
for (int i = p; i <= q; ++i) {
107+
if (order[i] == val) return i;
108+
}
109+
return 0;
110+
}
111+
}
46112
```
47113

48114
### **...**

‎solution/0100-0199/0105.Construct Binary Tree from Preorder and Inorder Traversal/README_EN.md

Lines changed: 56 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,13 +39,67 @@ inorder = [9,3,15,20,7]</pre>
3939
### **Python3**
4040

4141
```python
42-
42+
# Definition for a binary tree node.
43+
# class TreeNode:
44+
# def __init__(self, x):
45+
# self.val = x
46+
# self.left = None
47+
# self.right = None
48+
49+
class Solution:
50+
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
51+
def build(preorder, inorder, p1, p2, i1, i2) -> TreeNode:
52+
if p1 > p2 or i1 > i2:
53+
return None
54+
root_val = preorder[p1]
55+
pos = -1
56+
for i in range(i1, i2 + 1):
57+
if inorder[i] == root_val:
58+
pos = i
59+
break
60+
root = TreeNode(root_val)
61+
root.left = None if pos == i1 else build(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1)
62+
root.right = None if pos == i2 else build(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2)
63+
return root
64+
return build(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)
4365
```
4466

4567
### **Java**
4668

4769
```java
48-
70+
/**
71+
* Definition for a binary tree node.
72+
* public class TreeNode {
73+
* int val;
74+
* TreeNode left;
75+
* TreeNode right;
76+
* TreeNode(int x) { val = x; }
77+
* }
78+
*/
79+
class Solution {
80+
public TreeNode buildTree(int[] preorder, int[] inorder) {
81+
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
82+
}
83+
84+
private TreeNode buildTree(int[] preorder, int[] inorder, int p1, int p2, int i1, int i2) {
85+
if (p1 > p2 || i1 > i2) {
86+
return null;
87+
}
88+
int rootVal = preorder[p1];
89+
int pos = find(inorder, rootVal, i1, i2);
90+
TreeNode root = new TreeNode(rootVal);
91+
root.left = pos == i1 ? null : buildTree(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1);
92+
root.right = pos == i2 ? null : buildTree(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2);
93+
return root;
94+
}
95+
96+
private int find(int[] order, int val, int p, int q) {
97+
for (int i = p; i <= q; ++i) {
98+
if (order[i] == val) return i;
99+
}
100+
return 0;
101+
}
102+
}
49103
```
50104

51105
### **...**

‎solution/0100-0199/0105.Construct Binary Tree from Preorder and Inorder Traversal/Solution.java

Lines changed: 16 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
/**
22
* Definition for a binary tree node.
3-
* class TreeNode {
3+
* public class TreeNode {
44
* int val;
55
* TreeNode left;
66
* TreeNode right;
@@ -9,29 +9,25 @@
99
*/
1010
class Solution {
1111
public TreeNode buildTree(int[] preorder, int[] inorder) {
12-
if (preorder == null || inorder == null || preorder.length != inorder.length) {
12+
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
13+
}
14+
15+
private TreeNode buildTree(int[] preorder, int[] inorder, int p1, int p2, int i1, int i2) {
16+
if (p1 > p2 || i1 > i2) {
1317
return null;
1418
}
15-
int n = preorder.length;
16-
return n > 0 ? buildTree(preorder, 0, n - 1, inorder, 0, n - 1) : null;
19+
int rootVal = preorder[p1];
20+
int pos = find(inorder, rootVal, i1, i2);
21+
TreeNode root = new TreeNode(rootVal);
22+
root.left = pos == i1 ? null : buildTree(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1);
23+
root.right = pos == i2 ? null : buildTree(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2);
24+
return root;
1725
}
18-
19-
private TreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
20-
TreeNode node = new TreeNode(preorder[s1]);
21-
if (s1 == e1 && s2 == e2) {
22-
return node;
23-
}
2426

25-
int p = s2;
26-
while (inorder[p] != preorder[s1]) {
27-
++p;
28-
if (p > e2) {
29-
throw new IllegalArgumentException("Invalid input!");
30-
}
27+
private int find(int[] order, int val, int p, int q) {
28+
for (int i = p; i <= q; ++i) {
29+
if (order[i] == val) return i;
3130
}
32-
33-
node.left = p > s2 ? buildTree(preorder, s1 + 1, s1 - s2 + p, inorder, s2, p - 1) : null;
34-
node.right = p < e2 ? buildTree(preorder, s1 - s2 + p + 1, e1, inorder, p + 1, e2) : null;
35-
return node;
31+
return 0;
3632
}
3733
}

‎solution/0100-0199/0105.Construct Binary Tree from Preorder and Inorder Traversal/Solution.py

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# Definition for a binary tree node.
2+
# class TreeNode:
3+
# def __init__(self, x):
4+
# self.val = x
5+
# self.left = None
6+
# self.right = None
7+
8+
class Solution:
9+
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
10+
def build(preorder, inorder, p1, p2, i1, i2) -> TreeNode:
11+
if p1 > p2 or i1 > i2:
12+
return None
13+
root_val = preorder[p1]
14+
pos = -1
15+
for i in range(i1, i2 + 1):
16+
if inorder[i] == root_val:
17+
pos = i
18+
break
19+
root = TreeNode(root_val)
20+
root.left = None if pos == i1 else build(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1)
21+
root.right = None if pos == i2 else build(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2)
22+
return root
23+
return build(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)

0 commit comments

Comments
 (0)