993. Cousins in Binary Tree

, ,

DFS

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
private static class State {
    private int depth;
    private TreeNode parent;
    private boolean appeared;
}

public boolean isCousins(TreeNode root, int x, int y) {
    State state = new State();
    return dfs(state, null, 0, root, x, y);
}

private boolean dfs(State state, TreeNode parent, int depth, TreeNode node, int x, int y) {
    if (node == null) {
        return false;
    }

    if (node.val == x || node.val == y) {
        if (!state.appeared) {
            state.depth = depth;
            state.parent = parent;
            state.appeared = true;
        } else {
            return state.depth == depth && state.parent != parent;
        }
    }

    return dfs(state, node, depth + 1, node.left, x, y) || dfs(state, node, depth + 1, node.right, x, y);
}

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
27
28
29
30
31
class Solution {
    public boolean isCousins(TreeNode root, int x, int y) {
        TreeNode prevParent = null;
        int prevDepth = 0;

        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[]{root, null});
        for (int depth = 0; !queue.isEmpty(); depth++) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode[] nodes = queue.poll();
                TreeNode node = nodes[0], parent = nodes[1];
                if (node.val == x || node.val == y) {
                    if (prevParent != null) {
                        return prevParent != parent && prevDepth == depth;
                    } else {
                        prevParent = parent;
                        prevDepth = depth;
                    }
                }
                if (node.left != null) {
                    queue.offer(new TreeNode[]{node.left, node});
                }
                if (node.right != null) {
                    queue.offer(new TreeNode[]{node.right, node});
                }
            }
        }

        return false;
    }
}

References

993. Cousins in Binary Tree