leetcode：993. 二叉树的堂兄弟节点

题目

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

示例 1：
[简单] 993. 二叉树的堂兄弟节点 - 图1

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

示例 2：
[简单] 993. 二叉树的堂兄弟节点 - 图2

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

示例 3：
[简单] 993. 二叉树的堂兄弟节点 - 图3

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

解答 & 代码

解法一：层序遍历

层序遍历的过程中：

  1. 如果当前节点的两个孩子节点的值分别为 x 和 y，则直接返回 false，因为是亲兄弟节点而不是堂兄弟节点
  2. 如果一层中同时出现了值为 x 和 y 的节点，则直接返回 true（上面这一条规则已经过滤掉了亲兄弟的情况）

如果遍历结束，则返回 false，说明没有在同一层中同时找到 x 和 y，两者不是堂兄弟

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // 层序遍历
  15.     bool isCousins(TreeNode* root, int x, int y) {
  16.         if(root == nullptr)
  17.             return false;
  19.         queue<TreeNode*> nodeQ;
  20.         nodeQ.push(root);
  21.         while(!nodeQ.empty())
  22.         {
  23.             bool hasX = false;    // 当前层是否包含值为 x 的节点
  24.             bool hasY = false;    // 当前层是否包含值为 y 的节点
  25.             int levelSize = nodeQ.size();
  26.             for(int i = 0; i < levelSize; ++i)
  27.             {
  28.                 TreeNode* cur = nodeQ.front();
  29.                 nodeQ.pop();
  30.                 if(cur->val == x)
  31.                     hasX = true;
  32.                 if(cur->val == y)
  33.                     hasY = true;
  35.                 if(cur->left != nullptr)
  36.                     nodeQ.push(cur->left);
  37.                 if(cur->right != nullptr)
  38.                     nodeQ.push(cur->right);
  39.                 // 1. 如果当前节点的左右孩子的值分别为 x、y，则是亲兄弟节点，直接返回 false
  40.                 if(cur->left != nullptr && cur->right != nullptr &&
  41.                     ((cur->left->val == x && cur->right->val == y) || 
  42.                      (cur->left->val == y && cur->right->val == x)))
  43.                      return false;
  44.             }
  45.             // 2. 如果同一层中同时包含值为 x 和 y 的节点，则直接返回 true，是堂兄弟节点
  46.             if(hasX && hasY)
  47.                 return true;
  48.         }
  49.         return false;    // 3. 遍历结束，x、y 不在同一层，不是堂兄弟
  50.     }
  51. };

复杂度分析：设二叉树节点数为 n

  • 时间复杂度 O(n)：最坏情况下，遍历二叉树所有节点
  • 空间复杂度 O(n)：队列 nodeQ 的时间复杂度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 56.59% 的用户
  4. 内存消耗：10.8 MB, 在所有 C++ 提交中击败了 26.58% 的用户

解法二：DFS

DFS 分别找到 x 和 y 的父节点、深度，如果父节点不同、深度相同，则返回 true，否则返回 false

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     // DFS 寻找值为 x 的节点的深度及其父节点指针，分别存到 xDepth 和 xParent 
  15.     bool dfs(TreeNode* root, int x, int depth, TreeNode*& xParent, int& xDepth)
  16.     {
  17.         if(root == nullptr)
  18.             return false;
  20.         if((root->left != nullptr && root->left->val == x) ||
  21.             (root->right != nullptr && root->right->val == x))
  22.         {
  23.             xParent = root;
  24.             xDepth = depth + 1;
  25.             return true;
  26.         }
  27.         return dfs(root->left, x, depth + 1, xParent, xDepth) ||
  28.                 dfs(root->right, x, depth + 1, xParent, xDepth);
  29.     }
  30. public:
  31.     bool isCousins(TreeNode* root, int x, int y) {
  32.         TreeNode* xParent = nullptr;
  33.         TreeNode* yParent = nullptr;
  34.         int xDepth = 0;
  35.         int yDepth = 0;
  36.         // 分别找到值为 x、y 的节点的父节点、深度
  37.         bool findX = dfs(root, x, 0, xParent, xDepth);
  38.         bool findY = dfs(root, y, 0, yParent, yDepth);
  39.         // 如果 x、y 节点的父节点不同、深度相同，则返回 true，否则返回 false
  40.         return findX && findY && xParent != yParent && xDepth == yDepth;
  41.     }
  42. };

复杂度分析：设二叉树节点数为 n

  • 时间复杂度 O(n)：最坏情况下，遍历二叉树所有节点
  • 空间复杂度 O(log n)：递归站深度 ~ 二叉树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 56.59% 的用户
  4. 内存消耗：10.8 MB, 在所有 C++ 提交中击败了 39.42% 的用户