https://leetcode-cn.com/problems/cousins-in-binary-tree/
/*
* @Author: Goog Tech
* @Date: 2020-09-12 11:36:11
* @LastEditTime: 2020-09-12 11:36:33
* @Description: https://leetcode-cn.com/problems/cousins-in-binary-tree/
* @FilePath: \leetcode-googtech\#993. Cousins in Binary Tree\Solution.java
* @WebSite: https://algorithm.show/
*/
/**
* 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 {
Map<Integer, Integer> depth;
Map<Integer, TreeNode> parent;
// 解题思路: 利用深度优先搜索及递归求出每一个节点的深度与父节点
public boolean isCousins(TreeNode root, int x, int y) {
depth = new HashMap();
parent = new HashMap();
// 传入根节点及其父节点(null)
dfs(root, null);
// 当且仅当一对节点深度相同而父节点不同时,它们是堂兄弟节点.
return (depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y));
}
public void dfs(TreeNode node, TreeNode par) {
// 判断当前节点,即上一个节点的孩子节点是否为空
if(node != null) {
// 对于每一个节点 node,它的父亲为 par,深度为 d,我们将其记录到 HashMap 中
// 即令 parent[node.val] = par, depth[node.val] = d
depth.put(node.val, par != null ? 1 + depth.get(par.val) : 0);
parent.put(node.val, par);
// 传入当前节点的孩子节点及其父节点,即继续深度遍历
dfs(node.left, node);
dfs(node.right, node);
}
}
}
'''
Author: Goog Tech
Date: 2020-09-12 11:36:15
LastEditTime: 2020-09-12 11:36:59
Description: https://leetcode-cn.com/problems/cousins-in-binary-tree/
FilePath: \leetcode-googtech\#993. Cousins in Binary Tree\Solution.py
WebSite: https://algorithm.show/
'''
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
# 解题思路: 利用深度优先搜索及递归求出每一个节点的深度与父节点
def isCousins(self, root, x, y):
"""
:type root: TreeNode
:type x: int
:type y: int
:rtype: bool
"""
parent, depth = {}, {}
def dfs(node, par = None):
# 判断当前节点,即上一个节点的孩子节点是否为空
if node:
# 对于每一个节点 node,它的父亲为 par,深度为 d,我们将其记录到 HashMap 中
# 即令 parent[node.val] = par, depth[node.val] = d
depth[node.val] = 1 + depth[par.val] if par else 0
parent[node.val] = par
# 传入当前节点的孩子节点及其父节点,即继续深度遍历
dfs(node.left, node)
dfs(node.right, node)
dfs(root)
# 当且仅当一对节点深度相同而父节点不同时,它们是堂兄弟节点.
return depth[x] == depth[y] and parent[x] != parent[y]