【LeetCode】 993. Cousins in Binary Tree

Description

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.

Note:

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

在一個二元樹中，樹根節點的深度是0，每個深度為k的節點，他們的小孩深度為k+1。

二元樹中兩個節點如果是表親，則它們擁有一樣的深度但父親不同。

我們給予二元樹中的root且所有節點都有不同的值，還有兩個不同節點中的值x和y。

如果x和y對應的節點是表親的話，回傳true。

提示：

1. 樹擁有的節點數量介於 2 到 100。
2. 節點中不重複的值介於 1 到 100。

Example:

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

Solution

• 二元樹的遍歷中，大致可以分為四種方式：
  • 前序遍歷
  • 中序遍歷
  • 後序遍歷
  • 階層遍歷
• 其中階層遍歷是使用BFS去跑，而結果就會按照樹的深度去跑，這剛好就是我們要的。
• 我們只要使用BFS，跑到x或y時去紀錄深度和父親即可。
  • BFS的queue結構可以使用STL就好。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:    
    void BFS(int x, int y, int& dx, int& dy, TreeNode*& px, TreeNode*& py, queue<TreeNode*>& queueNode, queue<TreeNode*>& queueParents, queue<int>& queueDepth)
    {
        if(!queueNode.empty())
        {
            TreeNode* n = queueNode.front();
            queueNode.pop();
            int d = queueDepth.front();
            queueDepth.pop();
            TreeNode* p = queueParents.front();
            queueParents.pop();
                
            if(n->val == x) 
            {
                dx = d;
                px = p;
            }
            if(n->val == y)
            {
                dy = d;
                py = p;
            }
            
            if(px && py)
                return;
            
            if(n->left)
            {
                queueNode.push(n->left);
                queueDepth.push(d + 1);
                queueParents.push(n);
            }
            if(n->right)
            {
                queueNode.push(n->right);
                queueDepth.push(d + 1);
                queueParents.push(n);
            }
            BFS(x, y, dx, dy, px, py, queueNode, queueParents, queueDepth);
        }
    }
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> queueNode;
        queueNode.push(root);
        queue<TreeNode*> queueParents;
        queueParents.push(NULL);
        queue<int> queueDepth;
        queueDepth.push(0);
        int dx = -1;
        int dy = -1;
        TreeNode* px = NULL;
        TreeNode* py = NULL;
        
        BFS(x, y, dx, dy, px, py, queueNode, queueParents, queueDepth);
        return dx == dy && dx != -1 && px != py;
    }
};

tags: LeetCode C++