package leetcode;

/**
 * https://leetcode.com/problems/cousins-in-binary-tree/
 */
public class Problem993 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        // TODO
        return false;
    }

    public static void main(String[] args) {
        Problem993 prob = new Problem993();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.right = new TreeNode(3);
        System.out.println(prob.isCousins(root, 4, 3)); // false

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(5);
        System.out.println(prob.isCousins(root, 5, 4)); // true

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(3);
        System.out.println(prob.isCousins(root, 2, 3)); // false
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -388,143 +388,182 @@
     
-// TODO%0A        return false
+Map%3CInteger, DepthParent%3E map = new HashMap%3C%3E();%0A        traverse(root, x, y, 0, 0, map)
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem993 prob = new Problem993(
+DepthParent xdp = map.get(x);%0A        DepthParent ydp = map.get(y
 );%0A
-%0A
         
 Tree
@@ -562,592 +562,726 @@
     
-TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2)
+if (xdp.parent == ydp.parent) %7B%0A            return false;%0A        %7D%0A        return xdp.depth == ydp.depth
 ;%0A    
+%7D%0A%0A
     
-root.left.left = new TreeNode(4);%0A        root.right = new TreeNode(3);%0A        System.out.println(prob.isCousins(root, 4, 3)); // false%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.right = new TreeNode(4);%0A        root.right = new TreeNode(3);%0A        root.right.right = new TreeNode(5);%0A        System.out.println(prob.isCousins(root, 5, 4)); // true%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.right = new TreeNode(4
+private static class DepthParent %7B%0A        private final int depth;%0A        private final int parent;%0A%0A        public DepthParent(int depth, int parent) %7B%0A            this.depth = depth;%0A            this.parent = parent;%0A        %7D%0A    %7D%0A%0A    private static void traverse(TreeNode root, int x, int y, int parent, int depth,%0A                                 Map%3CInteger, DepthParent%3E map) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        int newDepth = depth + 1;%0A        map.put(root.val, new DepthParent(newDepth, parent));%0A        traverse(root.left, x, y, root.val, newDepth, map
 );%0A 
@@ -1287,16 +1287,25 @@
         
+traverse(
 root.rig
@@ -1310,92 +1310,41 @@
 ight
- = new TreeNode(3);%0A        System.out.println(prob.isCousins(root, 2, 3)); // false
+, x, y, root.val, newDepth, map);
 %0A   

Solve problem 993