https://leetcode.com/problems/cousins-in-binary-tree/
https://leetcode.com/problems/cousins-in-binary-tree/discuss/240081/Java-easy-to-understand-and-clean-solution
I would put
https://leetcode.com/problems/cousins-in-binary-tree/discuss/240081/Java-easy-to-understand-and-clean-solution
https://leetcode.com/problems/cousins-in-binary-tree/discuss/242789/Java-Summary-of-2-solutions
https://leetcode.com/problems/cousins-in-binary-tree/discuss/239376/Java-BFS-time-and-space-beat-100
The level-order traversal is the most time-efficient solution for this problem since we only go as deep as the first potential cousin. The memory complexity is
X. https://leetcode.com/problems/cousins-in-binary-tree/discuss/242789/Java-Summary-of-2-solutions
In a binary tree, the root node is at depth
0, and children of each depth k node are at depth k+1.
Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
We are 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:
- The number of nodes in the tree will be between
2and100. - Each node has a unique integer value from
1to100
https://leetcode.com/problems/cousins-in-binary-tree/discuss/240081/Java-easy-to-understand-and-clean-solution
I would put
getDepthAndParent inside an else. Then if x or y is found, you don't need to go deeper in the tree. TreeNode xParent = null;
TreeNode yParent = null;
int xDepth = -1, yDepth = -1;
public boolean isCousins(TreeNode root, int x, int y) {
getDepthAndParent(root, x, y, 0, null);
return xDepth == yDepth && xParent != yParent? true: false;
}
//get both the depth and parent for x and y
public void getDepthAndParent(TreeNode root, int x, int y, int depth, TreeNode parent){
if(root == null){
return;
}
if(root.val == x){
xParent = parent;
xDepth = depth;
}else if(root.val == y){
yParent = parent;
yDepth = depth;
} else {
getDepthAndParent(root.left, x, y, depth + 1, root);
getDepthAndParent(root.right, x, y, depth + 1, root); }
}https://leetcode.com/problems/cousins-in-binary-tree/discuss/240081/Java-easy-to-understand-and-clean-solution
Map<Integer, Integer> depth;
Map<Integer, TreeNode> parent;
public boolean isCousins(TreeNode root, int x, int y) {
depth = new HashMap();
parent = new HashMap();
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) {
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);
}
}
X.https://leetcode.com/problems/cousins-in-binary-tree/discuss/242789/Java-Summary-of-2-solutions
public static boolean isCousins(TreeNode root, int x, int y) {
if(root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
TreeNode xParent = null, yParent = null;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
while(size > 0){
TreeNode node = queue.poll();
if(node.left != null){
queue.offer(node.left);
if(node.left.val == x) xParent = node;
if(node.left.val == y) yParent = node;
}
if(node.right != null){
queue.offer(node.right);
if(node.right.val == x) xParent = node;
if(node.right.val == y) yParent = node;
}
--size;
if(xParent != null && yParent != null) break;
}
if(xParent != null && yParent != null) return xParent != yParent;
if((xParent != null && yParent == null) ||
(xParent == null && yParent != null)) return false;
}
return false;
}
public boolean isCousins(TreeNode root, int A, int B) {
if (root == null) return false;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
boolean isAexist = false;
boolean isBexist = false;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.val == A) isAexist = true;
if (cur.val == B) isBexist = true;
if (cur.left != null && cur.right != null) {
if (cur.left.val == A && cur.right.val == B) {
return false;
}
if (cur.left.val == B && cur.right.val == A) {
return false;
}
}
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
if (isAexist && isBexist) return true;
}
return false;
}The level-order traversal is the most time-efficient solution for this problem since we only go as deep as the first potential cousin. The memory complexity is
O(n/2) to accommodate the longest level, vs. O(h) for recursive solutions, where h is the height of the tree (could be n in the worst case).X. https://leetcode.com/problems/cousins-in-binary-tree/discuss/242789/Java-Summary-of-2-solutions
public boolean isCousins(TreeNode root, int x, int y) {
return findDepth(root,x,1) == findDepth(root,y,1) && !isSibling(root,x,y);
}
private boolean isSibling(TreeNode node, int x, int y) {
if(node == null) return false;
boolean check = false;
if(node.left != null && node.right != null){
check = (node.left.val == x && node.right.val == y) ||
(node.left.val == y && node.right.val == x);
}
return check || isSibling(node.left, x, y) || isSibling(node.right, x, y);
}
private int findDepth(TreeNode node, int val, int height) {
if(node == null) return 0;
if(node.val == val) return height;
return findDepth(node.left, val, height + 1) |
findDepth(node.right, val, height + 1);
}