LeetCode : 863. All Nodes Distance K in Binary Tree

[congr]

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

[congr]

[congr]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        ArrayList<Integer>[] adjList = new ArrayList[501];
        for (int i = 0; i<adjList.length; i++) adjList[i] = new ArrayList();

        TreeNode node = root;
        Stack<TreeNode> st = new Stack();
        st.push(node);
        while (!st.isEmpty()) {
            node = st.pop();

            if (node.right != null) {
                adjList[node.val].add(node.right.val);
                adjList[node.right.val].add(node.val);
                st.push(node.right);
            }

            if (node.left != null) {
                adjList[node.val].add(node.left.val);
                adjList[node.left.val].add(node.val);
                st.push(node.left);
            }
        }

        boolean[] visited = new boolean[501];
        Queue<Integer> q = new LinkedList();
        q.add(target.val);
        visited[target.val] = true;

        ArrayList<Integer> res = new ArrayList();
        int k = 0;
        while(!q.isEmpty()) {
            if (k > K) return res;
            for (int size = q.size(); size > 0; size--) {
                int here = q.remove();
                if (k == K) res.add(here);
                for (int there : adjList[here]) {
                    if (!visited[there]) {
                        q.add(there);
                        visited[there] = true;
                    }
                }   
            }
            k++;
        }

        return res;
    }
}