[LeetCode] 993. Cousins in Binary Tree

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Constraints:
The number of nodes in the tree is in the range [2, 100].
1 <= Node.val <= 100
Each node has a unique value.
x != y
x and y are exist in the tree.

二叉树的堂兄弟节点。

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

思路

这是一道树的遍历的基础题，这里我提供 BFS 和 DFS 两种解决办法。

BFS 的做法，我们从 queue 中弹出每个元素 cur 的时候，我们要去看 cur 的左右孩子的节点值是否等于 x 和 y，如果等于，则不满足父节点不同这个条件；如果 x 和 y 在同一层被找到但是父节点不一样，则说明它们是一对堂兄弟节点。

DFS 的做法是我需要以前序遍历的方式遍历整棵树，并用几个全局变量记录 x 和 y 的深度和他们各自的父节点。

复杂度

时间O(n)
空间O(n)

BFS代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	public boolean isCousins(TreeNode root, int x, int y) {
		// corner case
		if (root == null) {
			return false;
		}

		// normal case
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			boolean xflag = false;
			boolean yflag = false;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode cur = queue.poll();
				if (cur.val == x) {
					xflag = true;
				}
				if (cur.val == y) {
					yflag = true;
				}
				if (cur.left != null && cur.right != null) {
					if (cur.left.val == x && cur.right.val == y) {
						return false;
					}
					if (cur.left.val == y && cur.right.val == x) {
						return false;
					}
				}
				if (cur.left != null) {
					queue.offer(cur.left);
				}
				if (cur.right != null) {
					queue.offer(cur.right);
				}
			}
			if (xflag && yflag) {
				return true;
			}
		}
		return false;
	}
}

DFS代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode xParent = null;
    TreeNode yParent = null;
    int xDepth = -1;
    int yDepth = -1;

    public boolean isCousins(TreeNode root, int x, int y) {
        helper(root, x, y, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    private void helper(TreeNode root, int x, int y, int depth, TreeNode parent) {
        if (root == null) {
            return;
        }
        if (root.val == x) {
            xParent = parent;
            xDepth = depth;
        }
        if (root.val == y) {
            yParent = parent;
            yDepth = depth;
        }
        helper(root.left, x, y, depth + 1, root);
        helper(root.right, x, y, depth + 1, root);
    }
}

相关题目

993. Cousins in Binary Tree
2641. Cousins in Binary Tree II