Skip to content

Commit 5d0371e

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lcof problem
1 parent a863e7f commit 5d0371e

File tree

6 files changed

+66
-74
lines changed

6 files changed

+66
-74
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -95,6 +95,7 @@
9595
1. [路径总和](/solution/0100-0199/0112.Path%20Sum/README.md)
9696
1. [从前序与中序遍历序列构造二叉树](/solution/0100-0199/0105.Construct%20Binary%20Tree%20from%20Preorder%20and%20Inorder%20Traversal/README.md)
9797
1. [从中序与后序遍历序列构造二叉树](/solution/0100-0199/0106.Construct%20Binary%20Tree%20from%20Inorder%20and%20Postorder%20Traversal/README.md)
98+
1. [二叉搜索树的后序遍历序列](/lcof/面试题33.%20二叉搜索树的后序遍历序列/README.md)
9899
1. [二叉树的最近公共祖先](/solution/0200-0299/0235.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Search%20Tree/README.md)
99100
1. [二叉搜索树的最近公共祖先](/solution/0200-0299/0236.Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree/README.md)
100101

‎lcof/面试题26. 树的子结构/Solution.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Right *TreeNode
77
* }
88
*/
9-
func isSubStructure(A *TreeNode, B *TreeNode) bool {
9+
func isSubStructure(A *TreeNode, B *TreeNode) bool {
1010
// 约定空树不是任意一个树的子结构
1111
if A == nil || B == nil {
1212
return false

‎lcof/面试题33. 二叉搜索树的后序遍历序列/README.md

Lines changed: 32 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -49,17 +49,21 @@
4949
```python
5050
class Solution:
5151
def verifyPostorder(self, postorder: List[int]) -> bool:
52-
n = len(postorder)
53-
if n < 2:
52+
def verify(p1, p2):
53+
if p1 > p2:
54+
return True
55+
pos = p1
56+
while pos < p2 and postorder[pos] < postorder[p2]:
57+
pos += 1
58+
p = pos
59+
while pos < p2:
60+
if postorder[pos] < postorder[p2]:
61+
return False
62+
pos += 1
63+
return verify(p1, p - 1) and verify(p, p2 - 1)
64+
if not postorder:
5465
return True
55-
for i in range(n):
56-
if postorder[i] > postorder[-1]:
57-
break
58-
for j in range(i + 1, n - 1):
59-
if postorder[j] < postorder[-1]:
60-
return False
61-
return (i == 0 or self.verifyPostorder(postorder[:i])) and (i == n - 1 or self.verifyPostorder(postorder[i:-1]))
62-
66+
return verify(0, len(postorder) - 1)
6367
```
6468

6569
### **Java**
@@ -69,30 +73,21 @@ class Solution:
6973
```java
7074
class Solution {
7175
public boolean verifyPostorder(int[] postorder) {
72-
if (postorder.length == 0) {
73-
return true;
74-
}
75-
return verifyPostorder(postorder, 0, postorder.length - 1);
76+
int n;
77+
if (postorder == null || (n = postorder.length) == 0) return true;
78+
return verify(postorder, 0, n - 1);
7679
}
7780

78-
private boolean verifyPostorder(int[] postorder, int from, int to) {
79-
if (from == to) {
80-
return true;
81-
}
82-
int i = from, j = from;
83-
for (; i < to; ++i) {
84-
if (postorder[i] > postorder[to]) {
85-
break;
86-
}
81+
private boolean verify(int[] postorder, int p1, int p2) {
82+
if (p1 >= p2) return true;
83+
int pos = p1;
84+
while (pos < p2 && postorder[pos] < postorder[p2]) ++pos;
85+
int p = pos;
86+
while (pos < p2) {
87+
if (postorder[pos] < postorder[p2]) return false;
88+
++pos;
8789
}
88-
for (j = i + 1; j < to; ++j) {
89-
if (postorder[j] < postorder[to]) {
90-
return false;
91-
}
92-
}
93-
return (i == from || verifyPostorder(postorder, from, i - 1)) && (i == to || verifyPostorder(postorder, i, to - 1));
94-
95-
90+
return verify(postorder, p1, p - 1) && verify(postorder, p, p2 - 1);
9691
}
9792
}
9893
```
@@ -130,26 +125,26 @@ func verifyPostorder(postorder []int) bool {
130125
}
131126
return helper(postorder, 0, len(postorder)-1)
132127
}
133-
//递归
128+
// 递归
134129
func helper(postorder []int , left,right int) bool {
135130
if left >= right {
136131
return true
137132
}
138-
//最后一位即根
133+
// 最后一位即根
139134
rootValue := postorder[right]
140-
//从左开始往右遍历，直到大于根停止,小于部分是左子树
135+
// 从左开始往右遍历，直到大于根停止,小于部分是左子树
141136
i := left
142137
for i < right && postorder[i] < rootValue {
143138
i++
144139
}
145-
//剩下部分是右子树，检查是否都大于根值
140+
// 剩下部分是右子树，检查是否都大于根值
146141
for j := i; j < right; j++ {
147142
if postorder[j] < rootValue {
148143
return false
149144
}
150145
}
151-
l := helper(postorder,left,i-1) //检查左子树，左子树i要减一
152-
r := helper(postorder,i,right-1)//检查右子树，剔除最后一位是根
146+
l := helper(postorder,left,i-1) // 检查左子树，左子树i要减一
147+
r := helper(postorder,i,right-1)// 检查右子树，剔除最后一位是根
153148
return l && r
154149
}
155150
```

‎lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.go

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,25 +4,25 @@ func verifyPostorder(postorder []int) bool {
44
}
55
return helper(postorder, 0, len(postorder)-1)
66
}
7-
//递归
7+
// 递归
88
func helper(postorder []int , left,right int) bool {
99
if left >= right {
1010
return true
1111
}
12-
//最后一位即根
12+
// 最后一位即根
1313
rootValue := postorder[right]
14-
//从左开始往右遍历，直到大于根停止,小于部分是左子树
14+
// 从左开始往右遍历，直到大于根停止,小于部分是左子树
1515
i := left
1616
for i < right && postorder[i] < rootValue {
1717
i++
1818
}
19-
//剩下部分是右子树，检查是否都大于根值
19+
// 剩下部分是右子树，检查是否都大于根值
2020
for j := i; j < right; j++ {
2121
if postorder[j] < rootValue {
2222
return false
2323
}
2424
}
25-
l := helper(postorder,left,i-1) //检查左子树，左子树i要减一
26-
r := helper(postorder,i,right-1)//检查右子树，剔除最后一位是根
25+
l := helper(postorder,left,i-1) // 检查左子树，左子树i要减一
26+
r := helper(postorder,i,right-1)// 检查右子树，剔除最后一位是根
2727
return l && r
2828
}

‎lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.java

Lines changed: 12 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,28 +1,19 @@
11
class Solution {
22
public boolean verifyPostorder(int[] postorder) {
3-
if (postorder.length == 0) {
4-
return true;
5-
}
6-
return verifyPostorder(postorder, 0, postorder.length - 1);
3+
int n;
4+
if (postorder == null || (n = postorder.length) == 0) return true;
5+
return verify(postorder, 0, n - 1);
76
}
87

9-
private boolean verifyPostorder(int[] postorder, int from, int to) {
10-
if (from == to) {
11-
return true;
12-
}
13-
int i = from, j = from;
14-
for (; i < to; ++i) {
15-
if (postorder[i] > postorder[to]) {
16-
break;
17-
}
8+
private boolean verify(int[] postorder, int p1, int p2) {
9+
if (p1 >= p2) return true;
10+
int pos = p1;
11+
while (pos < p2 && postorder[pos] < postorder[p2]) ++pos;
12+
int p = pos;
13+
while (pos < p2) {
14+
if (postorder[pos] < postorder[p2]) return false;
15+
++pos;
1816
}
19-
for (j = i + 1; j < to; ++j) {
20-
if (postorder[j] < postorder[to]) {
21-
return false;
22-
}
23-
}
24-
return (i == from || verifyPostorder(postorder, from, i - 1))
25-
&& (i == to || verifyPostorder(postorder, i, to - 1));
26-
17+
return verify(postorder, p1, p - 1) && verify(postorder, p, p2 - 1);
2718
}
2819
}

‎lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.py

Lines changed: 14 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,17 @@
11
class Solution:
22
def verifyPostorder(self, postorder: List[int]) -> bool:
3-
n = len(postorder)
4-
if n < 2:
3+
def verify(p1, p2):
4+
if p1 > p2:
5+
return True
6+
pos = p1
7+
while pos < p2 and postorder[pos] < postorder[p2]:
8+
pos += 1
9+
p = pos
10+
while pos < p2:
11+
if postorder[pos] < postorder[p2]:
12+
return False
13+
pos += 1
14+
return verify(p1, p - 1) and verify(p, p2 - 1)
15+
if not postorder:
516
return True
6-
for i in range(n):
7-
if postorder[i] > postorder[-1]:
8-
break
9-
for j in range(i + 1, n - 1):
10-
if postorder[j] < postorder[-1]:
11-
return False
12-
return (i == 0 or self.verifyPostorder(postorder[:i])) and (i == n - 1 or self.verifyPostorder(postorder[i:-1]))
17+
return verify(0, len(postorder) - 1)

0 commit comments

Comments
 (0)