[LeetCode] 993. Cousins in Binary Tree

https://leetcode.com/problems/cousins-in-binary-tree/

Cousins in Binary Tree - LeetCode

Cousins in Binary Tree

 

 

이진 트리에서 주어진 두 수를 가진 노드들이 사촌관계인지 출력하는 문제이다.

사촌관계란, 루트 노드로부터 depth가 같아야하고, 부모가 서로 달라야한다.

 

풀이 방법은

루트부터 left, right 자식들을 훑으며 내려갈때마다 depth를 증가시켜 인자로 넣어주고, 파생된 부모노드 포인터도 인자로 넣어준다. 그러다 방문한 노드의 값이 주어진 값과 같을때, 각각 저장하고 두 값이 저장되어있을때 depth와 부모노드를 비교해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int xy[2];
    int depth[2] = {-1, -1};
    TreeNode* pre[2];
    bool isCousins(TreeNode* root, int x, int y) {
        this->xy[0] = x;
        this->xy[1] = y;
        run(root,0, NULL);
        return depth[0]!=-1 && depth[0]==depth[1] && pre[0]!=pre[1];
    }
    void run(TreeNode* node, int d, TreeNode* pre) {
        if (!node || (this->depth[0]!=-1 && this->depth[1] != -1)) return;
        for (int i=0; i<2; i++) if (this->xy[i]==node->val) {
            this->depth[i] = d;
            this->pre[i] = pre;
        }
        run(node->left, ++d, node);
        run(node->right, d, node);
    }
};