In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.
1.DFS , 深度优先搜索，记录宽度和父节点，并查看是否匹配
TreeNode xParent = null, yParent = null; int xDepth = -1, yDepth = -1; private void dfs(TreeNode root, TreeNode parent, int x, int y, int depth) { if (root == null) return; if (root.val == x) { //记录这个节点信息 xParent = parent; xDepath = depth; } if (root.val == y) { //记录这个节点信息 yParent = parent; yDepath = depth; } dfs(root.left, root, x, y, depth+1); dfs(root.right, root, x, y, depth+1); } BFS,宽度优先搜索在同一深度，如果只有一个节点，那么false； 如果有两个节点，考虑是否有同一个父节点，下面的解释讨论里的，来自https://leetcode.com/problems/cousins-in-binary-tree/discuss/239376/Java-BFS-time-and-space-beat-100 非常clear，个人认为比官方思路更清晰，直接在遍历的时候查看其子节点。官方是设置一个边界，如果超出边界那么就不是sibling。
public boolean isCousins(TreeNode root, int A, int B) { if (root == null) return false; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); boolean isAexist = false; boolean isBexist = false; for (int i = 0; i < size; i++) { TreeNode cur = queue.remove(); if (cur.val == A) isAexist = true; if (cur.val == B) isBexist = true; if (cur.left != null && cur.right != null) { //遍历到某个节点时，查看其两个子节点的值是否是A和B if (cur.left.val == A && cur.right.val == B) { return false; } if (cur.left.val == B && cur.right.val == A) { return false; } } //如果curr的两个子节点存在，添加至队列，然后进行下一次循环 if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } if (isAexist && isBexist) return true; } return false; }