题目描述

在一棵二叉树中，根结点的深度是 0，深度为 k 的结点的儿子深度为 k+1。

如果二叉树的两个结点有相同的深度，但不同的父亲，则称为兄弟姊妹 ( cousins ) 结点。

我们给定一棵二叉树的根结点，树中结点值都不相同，和两个树中不同的值 x 和 y。

返回 true 当且仅当值 x 和 y 对应的结点互为兄弟姊妹 (cousins)。

样例

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

注意

• 树中结点的个数在 2 和 100 之间。
• 每个结点唯一的值在 1 到 100 之间。

算法

(树的遍历) $O(n)$

1. 通过树的遍历，分别找到结点 x 和 y 的深度和对应的父亲。可以采用深度优先遍历或者宽度优先遍历。

时间复杂度

• 每个结点最多被访问常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 深度优先遍历需要额外 $O(h)$ 的栈空间，宽度优先遍历需要 $O(n)$ 的队列空间。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void dfs(TreeNode *rt, TreeNode *fa, int x, int depth, int &d, TreeNode* &f) {
        if (rt -> val == x) {
            d = depth;
            f = fa;
            return;
        }

        if (rt -> left != nullptr)
            dfs(rt -> left, rt, x, depth + 1, d, f);

        if (d == -1) {
            if (rt -> right != nullptr)
                dfs(rt -> right, rt, x, depth + 1, d, f);
        }
    }

    bool isCousins(TreeNode* root, int x, int y) {
        int dx = -1, dy = -1;
        TreeNode *fx, *fy;
        dfs(root, nullptr, x, 0, dx, fx);
        dfs(root, nullptr, y, 0, dy, fy);

        if (dx != dy)
            return false;
        return fx != fy;
    }
};