代码随想录算法训练营第十五天-110平衡二叉树 、257二叉树的所有路径、404左叶子之和
初步题解
110 平衡二叉树
题目链接：(https://leetcode.cn/problems/balanced-binary-tree/)
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
| public class LE110 {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
}
|
257 二叉树的所有路径
题目链接：(https://leetcode.cn/problems/binary-tree-paths/description/)
(不会)
404 左叶子之和
1
2
3
4
5
6
7
8
9
10
11
| public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
sum += root.left.val;
}
return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
|
看解析
110 平衡二叉树
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0110.平衡二叉树.html)
分别求出其左右子树的高度，然后如果差值小于等于 1，则返回当前二叉树的高度，否则返回 -1，表示已经不是二叉平衡树了。
257 二叉树的所有路径
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0257.二叉树的所有路径.html)
主要是这个回溯有点懵，不知道怎么写了。但是写完代码跟着断点跑一遍，可以看到：在有下个节点时，会一直递归，直到进入到最后一个节点。在返回的途中，会把所有的进入操作，回退回去（即回退到交叉节点那个位置）。可能表述的不是很清楚，写完代码跑一遍就清楚了。
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
| public static List<String> binaryTreePaths(TreeNode root) {
List<String> pathString = new ArrayList<>();
if (root == null) {
return pathString;
}
List<Integer> path = new ArrayList<>();
binaryTree(root, path, pathString);
return pathString;
}
private static void binaryTree(TreeNode root, List<Integer> path, List<String> pathString) {
path.add(root.val);
if (root != null && (root.right == null && root.left == null)) {
pathString.add(path.stream().map(Object::toString).collect(Collectors.joining("->")));
return;
}
if (root.left != null) {
binaryTree(root.left, path, pathString);
path.remove(path.size() - 1);
}
if (root.right != null) {
binaryTree(root.right, path, pathString);
path.remove(path.size() - 1);
}
}
|
404 左叶子之和
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0404.左叶子之和.html)