Skip to content

Commit a450b38

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lcof problems: No.054, 055-I
1 parent e2c7492 commit a450b38

File tree

10 files changed

+184
-124
lines changed

10 files changed

+184
-124
lines changed

‎lcof/面试题55 - I. 二叉树的深度/README.md

Lines changed: 38 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -79,38 +79,60 @@ class Solution {
7979
* @param {TreeNode} root
8080
* @return {number}
8181
*/
82-
var maxDepth = function (root) {
83-
let res = 0;
84-
function traversal(node, depth) {
85-
if (!node) {
86-
res = Math.max(res, depth);
87-
return;
82+
var maxDepth = function(root) {
83+
if (!root) {
84+
return 0;
8885
}
89-
traversal(node.left, depth + 1);
90-
traversal(node.right, depth + 1);
91-
}
92-
traversal(root, 0);
93-
return res;
86+
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
9487
};
9588
```
9689

9790
### **C++**
9891

9992
```cpp
93+
/**
94+
* Definition for a binary tree node.
95+
* struct TreeNode {
96+
* int val;
97+
* TreeNode *left;
98+
* TreeNode *right;
99+
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
100+
* };
101+
*/
100102
class Solution {
101103
public:
102104
int maxDepth(TreeNode* root) {
103-
if (nullptr == root) {
105+
if (!root) {
104106
return 0;
105107
}
106-
107-
int left = maxDepth(root->left);
108-
int right = maxDepth(root->right);
109-
return std::max(left, right) + 1;
108+
return 1 + max(maxDepth(root->left), maxDepth(root->right));
110109
}
111110
};
112111
```
113112
113+
### **Go**
114+
115+
```go
116+
/**
117+
* Definition for a binary tree node.
118+
* type TreeNode struct {
119+
* Val int
120+
* Left *TreeNode
121+
* Right *TreeNode
122+
* }
123+
*/
124+
func maxDepth(root *TreeNode) int {
125+
if (root == nil) {
126+
return 0
127+
}
128+
left, right := maxDepth(root.Left), maxDepth(root.Right)
129+
if left > right {
130+
return 1 + left
131+
}
132+
return 1 + right
133+
}
134+
```
135+
114136
### **...**
115137

116138
```

‎lcof/面试题55 - I. 二叉树的深度/Solution.cpp

Lines changed: 2 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -7,16 +7,12 @@
77
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
88
* };
99
*/
10-
1110
class Solution {
1211
public:
1312
int maxDepth(TreeNode* root) {
14-
if (nullptr == root) {
13+
if (!root) {
1514
return 0;
1615
}
17-
18-
int left = maxDepth(root->left);
19-
int right = maxDepth(root->right);
20-
return std::max(left, right) + 1;
16+
return 1 + max(maxDepth(root->left), maxDepth(root->right));
2117
}
2218
};

‎lcof/面试题55 - I. 二叉树的深度/Solution.go

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
9+
func maxDepth(root *TreeNode) int {
10+
if (root == nil) {
11+
return 0
12+
}
13+
left, right := maxDepth(root.Left), maxDepth(root.Right)
14+
if left > right {
15+
return 1 + left
16+
}
17+
return 1 + right
18+
}

‎lcof/面试题55 - I. 二叉树的深度/Solution.js

Lines changed: 5 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -9,16 +9,9 @@
99
* @param {TreeNode} root
1010
* @return {number}
1111
*/
12-
var maxDepth = function (root) {
13-
let res = 0;
14-
function traversal(node, depth) {
15-
if (!node) {
16-
res = Math.max(res, depth);
17-
return;
18-
}
19-
traversal(node.left, depth + 1);
20-
traversal(node.right, depth + 1);
12+
var maxDepth = function(root) {
13+
if (!root) {
14+
return 0;
2115
}
22-
traversal(root, 0);
23-
return res;
24-
};
16+
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
17+
};

‎lcof/面试题55 - II. 平衡二叉树/README.md

Lines changed: 67 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -54,14 +54,14 @@
5454

5555
class Solution:
5656
def isBalanced(self, root: TreeNode) -> bool:
57+
def height(root):
58+
if root is None:
59+
return 0
60+
return 1 + max(height(root.left), height(root.right))
61+
5762
if root is None:
5863
return True
59-
return abs(self._height(root.left) - self._height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
60-
61-
def _height(self, tree):
62-
if tree is None:
63-
return 0
64-
return 1 + max(self._height(tree.left), self._height(tree.right))
64+
return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
6565
```
6666

6767
### **Java**
@@ -81,14 +81,14 @@ class Solution {
8181
if (root == null) {
8282
return true;
8383
}
84-
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
84+
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
8585
}
8686

87-
private int height(TreeNode tree) {
87+
private int depth(TreeNode tree) {
8888
if (tree == null) {
8989
return 0;
9090
}
91-
return 1 + Math.max(height(tree.left), height(tree.right));
91+
return 1 + Math.max(depth(tree.left), depth(tree.right));
9292
}
9393
}
9494
```
@@ -107,59 +107,82 @@ class Solution {
107107
* @param {TreeNode} root
108108
* @return {boolean}
109109
*/
110-
var isBalanced = function (root) {
111-
if (!root) return true;
112-
if (!isBalanced(root.left) || !isBalanced(root.right)) return false;
113-
if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) return false;
114-
return true;
115-
};
110+
var isBalanced = function(root) {
111+
const depth = (root) => {
112+
if (!root) {
113+
return 0;
114+
}
115+
return 1 + Math.max(depth(root.left), depth(root.right));
116+
}
116117

117-
function getDepth(node) {
118-
if (!node) return 0;
119-
return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
120-
}
118+
if (!root) {
119+
return true;
120+
}
121+
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
122+
};
121123
```
122124

123125
### **C++**
124126

125127
```cpp
128+
/**
129+
* Definition for a binary tree node.
130+
* struct TreeNode {
131+
* int val;
132+
* TreeNode *left;
133+
* TreeNode *right;
134+
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
135+
* };
136+
*/
126137
class Solution {
127138
public:
128-
bool isBalanced(TreeNode* root, int* depth) {
129-
if (root == nullptr) {
130-
*depth = 0;
139+
bool isBalanced(TreeNode* root) {
140+
if (!root) {
131141
return true;
132142
}
133-
134-
int left = 0;
135-
int right = 0;
136-
if (isBalanced(root->left, &left) && isBalanced(root->right, &right)) {
137-
// 这样做的优势是，不用每次都计算单个子树的深度
138-
int diff = left - right;
139-
if (diff > 1 || diff < -1) {
140-
// 如果有一处不符合 -1 < diff < 1，则直接返回false
141-
return false;
142-
} else {
143-
// 如果符合，则记录当前深度，然后返回上一层继续计算
144-
*depth = max(left, right) + 1;
145-
return true;
146-
}
147-
}
148-
149-
return false; // 如果
143+
return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
150144
}
151145

152-
bool isBalanced(TreeNode* root) {
146+
private:
147+
int depth(TreeNode* root) {
153148
if (!root) {
154-
return true;
149+
return 0;
155150
}
156-
157-
int depth = 0;
158-
return isBalanced(root, &depth);
151+
return 1 + max(depth(root->left), depth(root->right));
159152
}
160153
};
161154
```
162155
156+
### **Go**
157+
158+
```go
159+
/**
160+
* Definition for a binary tree node.
161+
* type TreeNode struct {
162+
* Val int
163+
* Left *TreeNode
164+
* Right *TreeNode
165+
* }
166+
*/
167+
func isBalanced(root *TreeNode) bool {
168+
if (root == nil) {
169+
return true
170+
}
171+
return math.Abs(float64(depth(root.Left)-depth(root.Right))) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
172+
}
173+
174+
func depth(root *TreeNode) int {
175+
if (root == nil) {
176+
return 0
177+
}
178+
left, right := depth(root.Left), depth(root.Right)
179+
if (left > right) {
180+
return 1 + left
181+
}
182+
return 1 + right
183+
}
184+
```
185+
163186
### **...**
164187

165188
```

‎lcof/面试题55 - II. 平衡二叉树/Solution.cpp

Lines changed: 8 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -7,39 +7,20 @@
77
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
88
* };
99
*/
10-
1110
class Solution {
1211
public:
13-
bool isBalanced(TreeNode* root, int* depth) {
14-
if (root == nullptr) {
15-
*depth = 0;
12+
bool isBalanced(TreeNode* root) {
13+
if (!root) {
1614
return true;
1715
}
18-
19-
int left = 0;
20-
int right = 0;
21-
if (isBalanced(root->left, &left)
22-
&& isBalanced(root->right, &right)) {
23-
int diff = left - right;
24-
if (diff > 1 || diff < -1) {
25-
// 如果有一处不符合 -1 < diff < 1，则直接返回false
26-
return false;
27-
} else {
28-
// 如果符合，则记录当前深度，然后返回上一层继续计算
29-
*depth = max(left, right) + 1;
30-
return true;
31-
}
32-
}
33-
34-
return false; // 如果有一处已经确定不是平衡二叉树了，则直接返回false
16+
return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
3517
}
3618

37-
bool isBalanced(TreeNode* root) {
19+
private:
20+
int depth(TreeNode* root) {
3821
if (!root) {
39-
return true;
22+
return 0;
4023
}
41-
42-
int depth = 0;
43-
return isBalanced(root, &depth);
24+
return 1 + max(depth(root->left), depth(root->right));
4425
}
45-
};
26+
};

‎lcof/面试题55 - II. 平衡二叉树/Solution.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
9+
func isBalanced(root *TreeNode) bool {
10+
if (root == nil) {
11+
return true
12+
}
13+
return math.Abs(float64(depth(root.Left)-depth(root.Right))) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
14+
}
15+
16+
func depth(root *TreeNode) int {
17+
if (root == nil) {
18+
return 0
19+
}
20+
left, right := depth(root.Left), depth(root.Right)
21+
if (left > right) {
22+
return 1 + left
23+
}
24+
return 1 + right
25+
}

‎lcof/面试题55 - II. 平衡二叉树/Solution.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,13 +12,13 @@ public boolean isBalanced(TreeNode root) {
1212
if (root == null) {
1313
return true;
1414
}
15-
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
15+
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
1616
}
1717

18-
private int height(TreeNode tree) {
18+
private int depth(TreeNode tree) {
1919
if (tree == null) {
2020
return 0;
2121
}
22-
return 1 + Math.max(height(tree.left), height(tree.right));
22+
return 1 + Math.max(depth(tree.left), depth(tree.right));
2323
}
2424
}

0 commit comments

Comments
 (0)