993. Cousins in Binary Tree

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: 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 {
    public boolean isCousins(TreeNode root, int x, int y) {
        if(root == null){
            return false;
        }
        
        int depth = 0;
        int depth1 = 0;
        int depth2 = 0;
        TreeNode parent1 = null;
        TreeNode parent2 = null;
        
        Map<TreeNode, TreeNode> hmap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        hmap.put(root, null);
        
        while(queue.size() > 0){
            depth++;
            int size = queue.size();
            
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                
                if(node.left != null){
                    queue.offer(node.left);
                    hmap.put(node.left, node);
                }
                if(node.right != null){
                    queue.offer(node.right);
                    hmap.put(node.right, node);
                }
                
                if(node.val == x){
                    depth1 = depth;
                    parent1 = hmap.get(node);
                }
                if(node.val == y){
                    depth2 = depth;
                    parent2 = hmap.get(node);
                }
            }
        }
        
        return parent1 != parent2 && depth1 == depth2;
    }
}

/**
 * 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, TreeNode> hmap;
    
    public boolean isCousins(TreeNode root, int x, int y) {
        hmap = new HashMap<>();
        
        int depth1 = findDepth(root, x, 0);
        int depth2 = findDepth(root, y, 0);
        
        return hmap.get(x) != hmap.get(y) && depth1 == depth2;
    }
    
    public int findDepth(TreeNode node, int val, int depth){
        if(node == null){
            return 0;
        }
        
        if(node.left != null && node.left.val == val){
            hmap.put(val, node);
        }
        if(node.right != null && node.right.val == val){
            hmap.put(val, node);
        }
        
        if(node.val != val){
            int left = findDepth(node.left, val, depth + 1);
            int right = findDepth(node.right, val, depth + 1);
            
            return Math.max(left, right);
        }
        
        return depth + 1;
    }
}