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

迈不过友情╰ 2022-12-20 05:38 99阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
    
    如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
    
    我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
    
    只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

示例 1：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center]

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

示例 2：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center 1]

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

示例 3：

![在这里插入图片描述][20201110192727564.png_pic_center]

输入：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)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d64745220d7a47cbac63d1592dd619ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/fe36c8512b284962a329d2477d9e0611.png
[20201110192727564.png_pic_center]: /images/20221120/29eb8aad14734a8b8497fee16f3a65ad.png