Cousins in Binary Tree
In a binary tree, the root node is at depth0
, and children of each depthk
node are at depthk+1
.
Two nodes of a binary tree are_cousins_if they have the same depth, but have different parents.
We are given theroot
of a binary tree with unique values, and the valuesx
andy
of two different nodes in the tree.
Return true
if and only if the nodes corresponding to the valuesx
andy
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
直接暴力做吧,依据:深度一样,parent不一样,分别存一下吧
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<Integer, TreeNode> parent = new HashMap<>(); // key: val of node, val: parent node
Map<Integer, Integer> depth = new HashMap<>(); // key: val of node, val: depth
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root, null);
return depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y);
}
private void dfs(TreeNode root, TreeNode par) {
if (root == null) {
return;
}
parent.put(root.val, par);
depth.put(root.val, par == null ? 0 : 1 + depth.get(par.val));
dfs(root.left, root);
dfs(root.right, root);
}
}
Last updated