993

993. Cousins in Binary Tree (Easy)

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.

Companies:
Amazon, Microsoft

Related Topics:
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Similar Questions:

• Binary Tree Level Order Traversal (Medium)

Solution 1. BFS

// OJ: https://leetcode.com/problems/cousins-in-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root->val == x || root->val == y) return false;
        queue<pair<TreeNode*, TreeNode*>> q;
        q.emplace((TreeNode*)NULL, root);
        while (q.size()) {
            int cnt = q.size();
            TreeNode *a = NULL, *b = NULL;
            while (cnt--) {
                auto p = q.front();
                q.pop();
                if (p.second->val == x) a = p.first;
                if (p.second->val == y) b = p.first;
                if (p.second->left) q.emplace(p.second, p.second->left);
                if (p.second->right) q.emplace(p.second, p.second->right);
            }
            if (a || b) return a && b && a != b;
        }
        return false;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/cousins-in-binary-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    pair<int, int> find(TreeNode *root, int val, int depth = 0, int parent = -1) {
        if (!root) return {-1, -1};
        if (root->val == val) return {depth, parent};
        auto left = find(root->left, val, depth + 1, root->val);
        return left.first != -1 ? left : find(root->right, val, depth + 1, root->val);
    }
public:
    bool isCousins(TreeNode* root, int x, int y) {
        auto [d1, p1] = find(root, x);
        auto [d2, p2] = find(root, y);
        return d1 == d2 && p1 != p2;
    }
};