題目： LeetCode - 993. Cousins in Binary Tree

題目說明

給一個 Binary Tree，兩個值，求該值是否在同一層且父節點不同。

解題思路

使用 pair<int, int> 紀錄，first 放父節點的值，second 放深度。再使用遞迴計算即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    pair<int, int> get(TreeNode* root, int target, int depth, int father)
    {
        if(!root)
            return {father, -1};
        if(root->val == target)
            return {father, depth};
        auto left = get(root->left, target, ++depth, root->val);
        if(left.second != -1)
            return left;
        return get(root->right, target, depth, root->val);
    }
    bool isCousins(TreeNode* root, int x, int y) {
        auto xInfo = get(root, x, 0, root->val);
        auto yInfo = get(root, y, 0, root->val);
        if(xInfo.first != yInfo.first && xInfo.second == yInfo.second)
            return true;
        return false;
    }
};