C语言重构【993】二叉树的堂兄弟节点

文章目录

所有题目源代码：Git地址

题目

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

 

示例 1：

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

示例 2：

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

示例 3：

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

提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

方案：

• 讨论下不同情况吧

class Solution
{
public:
    bool isCousins(TreeNode *root, int x, int y)
    {
        return calDepth(root, x, y, 0) == 0 ? true : false;
    }
    //找到各节点的深度并返回
    //没找到返回-1
    //找到了，但在同一父节点下，返回-1（两个返回depth都为1）
    //找到了，且值是相同且>1则是符合条件的
    int calDepth(TreeNode *root, int x, int y, int depth)
    {
        //如果没找到，直接返回-1
        if (root == NULL)
            return -1;
        //如果找到，直接返回1
        if (root->val == x || root->val == y)
            return 1;
        //这里默认元素只出现一次
        int left = calDepth(root->left, x, y, depth + 1);
        int right = calDepth(root->right, x, y, depth + 1);
        if (left == 0 || right == 0 || (left == right && left > 1))
            return 0;
        else if (left != right && (left == -1 || right == -1))
            return max(left, right) + 1;
        else if (left == right && left == 1)
            return -1;
        return -1;
    }
};

复杂度计算

• 时间复杂度：O(n)
• 空间复杂度：O(1)