[leetcode 993] Cousins in Binary Tree

- 두 노드가 부모가 다르고 같은 depth를 가진 cousin인지 확인하기 

 

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

 

- 일반적인 트리 순회이다.

- 트리 순회를 하면서 부모 노드와 depth를 저장하는 것이 핵심

/**
 * 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) {}
 * };
 */

using namespace std;

class Solution {
public:
    
    TreeNode* getParentAndDepth(TreeNode* root, int x, int& res){
        
        queue <tuple<TreeNode*, TreeNode*, int>> q;
        q.push(make_tuple(nullptr, root, 0));
                
        while(!q.empty()){
            TreeNode* par = get<0>(q.front());
            TreeNode* cur = get<1>(q.front());
            int curDepth = get<2>(q.front());
            q.pop();
           
            
            if(cur != nullptr){
                 
                if(cur->val == x){
                   res = curDepth;
                    return par;
                }
                
                if(cur->left != nullptr || cur->right != nullptr){
                    q.push(make_tuple(cur, cur->left, curDepth+1));
                    q.push(make_tuple(cur, cur->right, curDepth+1));
                }
            }
        }
        
       res = -1;
        return nullptr;
    }
    
    bool isCousins(TreeNode* root, int x, int y) {
        
        TreeNode *parX;
        TreeNode *parY;
        int depX=0, depY=0;
        
        parX = getParentAndDepth(root, x, depX);
        
        parY = getParentAndDepth(root, y,depY);
        
        if(depX == depY && parX!=parY){
            return true;
        }else {
            return false;
        }
    }
};