[LeetCode] 993. Cousins in Binary Tree

[grandyang]

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.

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 will be between 2 and 100.
• Each node has a unique integer value from 1 to 100.

这道题定义了一种二叉树数的表兄弟结点，就是不属于同一个父结点，但是深度相同，现在给了两个结点值，问它们代表的结点是否是表兄弟结点。由于表兄弟结点一定是属于同一层的，所以可以使用二叉树的层序遍历，就像之前那道 Binary Tree Level Order Traversal 一样。这里额外需要两个布尔型变量 isX，isY 来记录x和y是否已经遍历到了。由于是层序遍历，所以 while 中需要有个 for 循环，在循环中，取出队首结点，然后看结点值是否等于x或y，是的话标记布尔变量。然后检查当前结点的左右子结点是否分别是x和y，是的话直接返回 false。否则将左右子结点排入队列之中，若存在的话。当前层遍历完了之后，检查 isX 和 isY 的值，若同时为 true，表示存在表兄弟结点，返回 true。若只有一个为 true 的话，说明二者不在同一层，直接返回 false，参见代码如下：

解法一：

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> q{{root}};
        bool isX = false, isY = false;
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                TreeNode *cur = q.front(); q.pop();
                if (cur->val == x) isX = true;
                if (cur->val == y) isY = true;
                if (cur->left && cur->right) {
                    int left = cur->left->val, right = cur->right->val;
                    if ((left == x && right == y) || (left == y && right == x)) return false;
                }
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            if (isX && isY) return true;
            if (isX || isY) return false;
        }
        return false;
    }
};

当然我们也可以用递归的方法来做，由于不能同时处理同一层的结点，就需要两个变量 depthX 和 depthY 来记录结点x和y的深度，同时再用个布尔变量 sameParent 来记录这两个结点是否有相同的父结点。在递归函数中，若当前结点 node 为空，直接返回。若当前结点值是x，则 depthX 赋值为当前深度 cur，同理，若当前结点值是y，则 depthY 赋值为当前深度 cur。然后检查当前结点的左右子结点是否分别是x和y，是的话 sameParent 标记为 true，最后分别对左右子结点调用递归即可，参见代码如下：

解法二：

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        int depthX = 0, depthY = 0;
        bool sameParent = false;
        helper(root, x, y, 0, depthX, depthY, sameParent);
        return !sameParent && depthX == depthY;
    }
    void helper(TreeNode* node, int x, int y, int cur, int& depthX, int& depthY, bool& sameParent) {
        if (!node) return;
        if (node->val == x) depthX = cur;
        if (node->val == y) depthY = cur;
        if (node->left && node->right) {
            int left = node->left->val, right = node->right->val;
            if ((left == x && right == y) || (left == y && right == x)) sameParent = true;
        }
        helper(node->left, x, y, cur + 1, depthX, depthY, sameParent);
        helper(node->right, x, y, cur + 1, depthX, depthY, sameParent);
    }
};

接下来这种方法是博主在 Contest 时想出来的，思路比较简单粗暴，就是建立每个结点和其深度跟父结点组成的 pair 对儿之间的映射，然后就可以直接用x和y去获得其深度和父结点进行比较即可，参见代码如下：

解法三：

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
		unordered_map<int, pair<int, int>> m;
		helper(root, 0, -1, m);
		return m[x].first == m[y].first && m[x].second != m[y].second;
    }
    void helper(TreeNode* node, int depth, int parent, unordered_map<int, pair<int, int>>& m) {
    	if (!node) return;
    	m[node->val] = {depth, parent};
    	helper(node->left, depth + 1, node->val, m);
    	helper(node->right, depth + 1, node->val, m);
    }
};

Github 同步地址:

#993

类似题目：

Binary Tree Level Order Traversal

参考资料：

https://leetcode.com/problems/cousins-in-binary-tree/

https://leetcode.com/problems/cousins-in-binary-tree/discuss/238536/My-Easy-Recursive-C%2B%2B-Solution

https://leetcode.com/problems/cousins-in-binary-tree/discuss/239376/Java-BFS-time-and-space-beat-100

LeetCode All in One 题目讲解汇总(持续更新中...)