100. Same Tree
https://leetcode.com/problems/same-tree/
1
2
3
4
5
6
7
8
9
10
11
12
| public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
|
101. Symmetric Tree
https://leetcode.com/problems/symmetric-tree/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return check(p.left, q.right) && check(p.right, q.left);
}
|
104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
1
2
3
4
5
6
7
8
| public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
|
110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/
（第一回做的时候，犯了个小错误，求出leftDepth及rightDepth为 null 时，需要立即退出返回 null。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return depth(root) != null;
}
private Integer depth(TreeNode root) {
if (root == null) {
return 0;
}
Integer leftDepth = depth(root.left);
if (leftDepth == null) {
return null;
}
Integer rightDepth = depth(root.right);
if (rightDepth == null) {
return null;
}
if (Math.abs(leftDepth - rightDepth) > 1) {
return null;
}
return Math.max(leftDepth, rightDepth) + 1;
}
|
111. Minimum Depth of Binary Tree
https://leetcode.com/problems/minimum-depth-of-binary-tree/
与求最大高度相比，求最小高度特别之处在于：如果左右有一个高度为 0，则另一个的高度即为返回值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (leftDepth == 0) {
return rightDepth + 1;
}
if (rightDepth == 0) {
return leftDepth + 1;
}
return Math.min(leftDepth, rightDepth) + 1;
}
|
572. Subtree of Another Tree
https://leetcode.com/problems/subtree-of-another-tree/
我这里是想先层次遍历找到值相同的点后，再检验两个树是否相等。当然也可以使用isSubtree(s.left, t) || isSubtree(s.right, t)的形式递归判断。
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
| public boolean isSubtree(TreeNode s, TreeNode t) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(s);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null && t != null && node.val == t.val && check(node, t)) {
return true;
}
if (node != null && node.left != null) {
queue.offer(node.left);
}
if (node != null && node.right != null) {
queue.offer(node.right);
}
}
return false;
}
private boolean check(TreeNode n1, TreeNode n2) {
if (n1 == null && n2 == null) {
return true;
}
if (n1 == null || n2 == null) {
return false;
}
if (n1.val != n2.val) {
return false;
}
return check(n1.left, n2.left) && check(n1.right, n2.right);
}
|
递归的做法如下（可以看作是先序递归遍历）：
1
2
3
4
5
| public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (check(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
|
965. Univalued Binary Tree
https://leetcode.com/problems/univalued-binary-tree/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public boolean isUnivalTree(TreeNode root) {
if (root == null) {
return true;
}
int temp = root.val;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.val != temp) {
return false;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return true;
}
|
