993. Cousins in Binary Tree

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation