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.

这题求特定两个节点是否是cousin节点，也就是同级不同父节点的两个节点，所以适合使用广度优先遍历。

class CousinsInBinaryTree : public Solution {
public:
    void Execute() {
        TreeNode *root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->right = new TreeNode(4);
        root->right->right = new TreeNode(5);

        std::cout << "Case 1: " << isCousins(root, 5, 4);
    }

    bool isCousins(TreeNode* root, int x, int y) {
        if (nullptr == root || root->val == x || root->val == y) {
            return false;
        }

        vector<TreeNode *> parents = {root};
        vector<TreeNode *> children;

        while (!parents.empty()) {
            TreeNode *xp = nullptr, *yp = nullptr;

            for (auto v : parents) {
                // Get child
                if (nullptr != v->left) {
                    if (v->left->val == x) {
                        xp = v;
                    } else if (v->left->val == y) {
                        yp = v;
                    }
                    children.push_back(v->left);
                }
                if (nullptr != v->right) {
                    if (v->right->val == x) {
                        xp = v;
                    } else if (v->right->val == y) {
                        yp = v;
                    }
                    children.push_back(v->right);
                }
            }

            if (nullptr != xp && nullptr != yp && xp != yp) {
                return true;
            }
            if (nullptr != xp || nullptr != yp) {
                return false;
            }

            parents = std::move(children);
        }

        return false;
    }
};