package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
 */
public class Problem863 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        // TODO
        return null;
    }

    public static void main(String[] args) {
        Problem863 prob = new Problem863();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        System.out.println(prob.distanceK(root, root.left, 2)); // [7,4,1]
    }
}

@@ -12,16 +12,73 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.LinkedList;%0A
 import j
@@ -353,32 +353,280 @@
        %7D%0A    %7D%0A%0A
+    private static class TreeNodeIndex %7B%0A        private final int index;%0A        private final TreeNode node;%0A%0A        public TreeNodeIndex(int index, TreeNode node) %7B%0A            this.index = index;%0A            this.node = node;%0A        %7D%0A    %7D%0A%0A
     public List%3C
@@ -697,250 +697,491 @@
     
-// TODO%0A        return null
+List%3CTreeNode%3E%5B%5D graph = new List%5B501%5D;%0A        buildGraph(root, null, graph)
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem863 prob = new Problem863();%0A        TreeNode root = new TreeNode(3);%0A        root.left = new TreeNode(5);%0A        root.left.left = new TreeNode(6
+List%3CInteger%3E result = new ArrayList%3C%3E();%0A        LinkedList%3CTreeNodeIndex%3E queue = new LinkedList%3C%3E();%0A        boolean%5B%5D visited = new boolean%5B501%5D;%0A        queue.add(new TreeNodeIndex(0, target));%0A        visited%5Btarget.val%5D = true;%0A        while (!queue.isEmpty()) %7B%0A            TreeNodeIndex tni = queue.removeFirst();%0A            if (tni.index == K) %7B%0A                result.add(tni.node.val
 );%0A 
@@ -1191,88 +1191,385 @@
     
+ 
-root.left.right = new TreeNode(2);%0A        root.left.right.left = new TreeNode(7
+   %7D else if (tni.index %3E K) %7B%0A                break;%0A            %7D%0A            if (graph%5Btni.node.val%5D == null) %7B%0A                continue;%0A            %7D%0A            for (TreeNode adjacent : graph%5Btni.node.val%5D) %7B%0A                if (visited%5Badjacent.val%5D) %7B%0A                    continue;%0A                %7D%0A                queue.add(new TreeNodeIndex(tni.index + 1, adjacent)
 );%0A 
@@ -1579,116 +1579,551 @@
     
+  
-root.left.right.right = new TreeNode(4);%0A        root.right = new TreeNode(1);%0A        root.right.left = new
+      visited%5Badjacent.val%5D = true;%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static void buildGraph(TreeNode node,%0A                                   TreeNode parent,%0A                                   List%3CTreeNode%3E%5B%5D graph) %7B%0A        if (node == null) %7B%0A            return;%0A        %7D%0A        add(graph, node, parent);%0A        add(graph, parent, node);%0A        buildGraph(node.left, node, graph);%0A        buildGraph(node.right, node, graph);%0A    %7D%0A%0A    private static void add(List%3CTreeNode%3E%5B%5D graph, TreeNode from,
  Tre
@@ -2131,12 +2131,14 @@
 Node
-(0);
+ to) %7B
 %0A   
@@ -2146,118 +2146,289 @@
     
-root.right.right
+if (from == null %7C%7C to == null) %7B%0A            return;%0A        %7D%0A        if (graph%5Bfrom.val%5D
  =
+=
  n
-ew TreeNode(8);%0A        System.out.println(prob.distanceK(root, root.left, 2)); // %5B7,4,1%5D
+ull) %7B%0A            List%3CTreeNode%3E list = new ArrayList%3C%3E();%0A            list.add(to);%0A            graph%5Bfrom.val%5D = list;%0A        %7D else %7B%0A            graph%5Bfrom.val%5D.add(to);%0A        %7D
 %0A   

Solve problem 863