05 August 2008
判断两个结点在二叉树中是否是堂兄弟结点（深度相同，父结点不同）
两个方法均为O(n)和O(n)
BFS
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
public boolean isCousins(TreeNode root, int x, int y) {
Deque<TreeNode[]> q = new LinkedList<>();
q.offer(new TreeNode[]{root, null});
while (!q.isEmpty()) {
int size = q.size();
int fx = 0, fy = 0;
TreeNode[] candidates = new TreeNode[2];
for (int i = 0; i < size; i++) {
TreeNode[] poll = q.poll();
TreeNode cur = poll[0], parent = poll[1];
if (cur.val == x) {
fx = 1;
candidates[0] = parent;
} else if (cur.val == y) {
fy = 1;
candidates[1] = parent;
}
if (cur.left != null) q.offer(new TreeNode[]{cur.left, cur});
if (cur.right != null) q.offer(new TreeNode[]{cur.right, cur});
}
if ((fx | fy) ==0 ) continue;
if ((fx ^ fy) == 1) return false;
if ((fx & fy) == 1) return candidates[0] != candidates[1];
}
return false;
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean isCousins(TreeNode root, int x, int y) {
int[] xi = dfs(root, null, 0, x);
int[] yi = dfs(root, null, 0, y);
return xi[1] == yi[1] && xi[0] != yi[0];
}
int[] dfs(TreeNode root, TreeNode fa, int depth, int t) {
if (root == null) return new int[]{-1, -1}; // 使用 -1 代表为搜索不到 t
if (root.val == t) {
return new int[]{fa != null ? fa.val : 1, depth}; // 使用 1 代表搜索值 t 为 root
}
int[] l = dfs(root.left, root, depth + 1, t);
if (l[0] != -1) return l;
return dfs(root.right, root, depth + 1, t);
}
}