题目地址：https://leetcode.com/problems/cousins-in-binary-tree/
题目描述
Ina binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
Twonodes of a binary tree are cousins if they have the same depth, but have different parents.
Weare given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
Return true if and only if the nodes corresponding to the values x and y are cousins.
Example 1:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
Example 2:
Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true
Example 3:
Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false
Note:
1、 Thenumberofnodesinthetreewillbebetween2and100.；
2、 Eachnodehasauniqueintegervaluefrom1to100.；
题目大意
如果一个二叉树中的两个节点的父亲不同，但是高度相同，那么这两个节点是堂兄弟。判断给出的两个值为x和y的节点是不是堂兄弟。
解题方法
DFS
如果做过987. Vertical Order Traversal of a Binary Treeopen in new window，那么这个题肯定很快就能写出来。
题目要求的判断条件有两个1.父节点不同，2.高度相同，所以最直白的方法就是把每个节点的父节点和高度都求出来，然后判断x和y这两个节点是不是符合要求即可。
这个题中每个节点的值都不会重复，所以可以直接用值当做key来存储，代码很简单。
python代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isCousins(self, root, x, y):
"""
:type root: TreeNode
:type x: int
:type y: int
:rtype: bool
"""
self.m = collections.defaultdict(tuple)
self.dfs(root, None, 0)
px, dx = self.m[x]
py, dy = self.m[y]
return dx == dy and px != py
def dfs(self, root, parent, depth):
if not root: return
self.m[root.val] = (parent, depth)
self.dfs(root.left, root, depth + 1)
self.dfs(root.right, root, depth + 1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
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:
bool isCousins(TreeNode* root, int x, int y) {
m_.clear();
dfs(root, nullptr, 0);
auto px = m_[x], py = m_[y];
return px.first != py.first && px.second == py.second;
}
private:
unordered_map<int, pair<TreeNode*, int>> m_;
void dfs(TreeNode* root, TreeNode* parent, int depth) {
if (!root) return;
m_[root->val] = make_pair(parent, depth);
dfs(root->left, root, depth + 1);
dfs(root->right, root, depth + 1);
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
BFS
相似的，BFS也可以做，不过更简单一点的是不用在队列里保存每个节点的高度了，因为在BFS中搜完每一层才向下一层搜索，所以可以很方便的计算每个节点的高度。
Python代码如下：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isCousins(self, root, x, y):
"""
:type root: TreeNode
:type x: int
:type y: int
:rtype: bool
"""
m = collections.defaultdict(tuple)
q = collections.deque()
q.append((root, None))
depth = 0
while q:
size = len(q)
for i in range(size):
node, p = q.popleft()
if not node: continue
m[node.val] = (p, depth)
q.append((node.left, node))
q.append((node.right, node))
depth += 1
px, dx = m[x]
py, dy = m[y]
return dx == dy and px != py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
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:
bool isCousins(TreeNode* root, int x, int y) {
queue<pair<TreeNode*, TreeNode*>> q;
q.push(make_pair(root, nullptr));
unordered_map<int, pair<TreeNode*, int>> m_;
int depth = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto p = q.front(); q.pop();
if (!p.first) continue;
m_[p.first->val] = make_pair(p.second, depth);
q.push(make_pair(p.first->left, p.first));
q.push(make_pair(p.first->right, p.first));
}
++depth;
}
auto px = m_[x], py = m_[y];
return px.first != py.first && px.second == py.second;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发