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

堂兄弟节点"/>

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

题目来源

993. 二叉树的堂兄弟节点

题目描述

题目解析

要想判断两个节点 x x x 和 y y y 是否为堂兄弟节点，我们就需要求出这两个节点分别的「深度」以及「父节点」。

关键点是：

• 深度相同
• 父节点不同

广度优先遍历

在确定深度上面，BFS一直都是很可以的

具体思路： 因为在BFS中，我们使用的是层次遍历，如果每次遍历一层，那么这一层的元素的深度是相同的

第一层：[1]
第二层：[2,3]
第三层：[4,5,6,7]

因此，我们在每一层，看看是否有出现x和y，其中分为下面几种情况

• x和y都没有出现 —> 那就只能往下一层继续找了
• x和y只出现了一个 —> 两个元素的深度不同，不可能为兄弟，返回false
• x 和 y 都出现了
  • x 和 y 父节点相同 → 不是堂兄弟，是亲兄弟，不行，返回false
  • x 和 y 父节点不同 → 满足题目条件了，返回true

众所周知，BFS需要用到队列，那么我们应该如何设计队列的数据类型？可以采用pair<TreeNode*, TreeNode*>（其实pair<TreeNode*, int>也可以），其中pair中，第一个元素记录指向当前结点的指针，第二个元素记录指向当前结点的父结点的指针，这样就可以完美应对上面所说的三种情况了。

bool isCousins(TreeNode* root, int x, int y) {if(root == NULL){return false;}std::queue<std::pair<TreeNode*, TreeNode *>> queue;queue.push({root, NULL});while (!queue.empty()){std::vector<TreeNode *> rec_parent;  // 存储 {x, y}的父节点int size = queue.size();for (int i = 0; i < size; ++i) {std::pair<TreeNode*, TreeNode *> peek = queue.front();TreeNode* node = peek.first, *parent = peek.second;queue.pop();if(node->val == x || node->val == y){rec_parent.emplace_back(parent);}if(node->left){queue.push({node->left, node});}if(node->right){queue.push({node->right, node});}}if(rec_parent.empty()){  //  `x` 和 `y` 都没出现continue;}else if(rec_parent.size() == 1){   //`x` 和 `y` 只出现一个return false;}else if(rec_parent.size() == 2){  //`x` 和 `y` 都出现了return rec_parent[0] != rec_parent[1];    // `x` 和 `y` 父节点 相同/不相同 ？}}return false;
}

深度优先遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int dx, dy;private TreeNode px, py;public boolean isCousins(TreeNode root, int x, int y) {if (root == null || root.val ==x || root.val == y){return false;}helper(root, x, y, 0);return dx == dy && px != null && py != null && px.val != py.val;}private void helper(TreeNode node, int x, int y, int depth){if (node.left != null){if (node.left.val == x){dx = depth;px = node;}else if (node.left.val == y){dy = depth;py = node;}helper(node.left, x, y, depth + 1);}if (px != null && py != null){return;}if (node.right != null){if (node.right.val == x){dx = depth;px = node;}else if (node.right.val == y){dy = depth;py = node;}helper(node.right, x, y, depth + 1);}}
}