Faster than 99.69% | Memory 94.4% | Path to target + function to find nodes distance k down the tree
Intuition\nInstead of making pointers to all parents, we only need pointers to parents of target, which is the same as just having the path from root to target.
# Intuition\nInstead of making pointers to all parents, we only need pointers to parents of target, which is the same as just having the path from root to target.\n\n# Approach\nGet the path root to target.\nCreate a function to find all values at distance k (searching down the tree): distanceK(node, k). \nCall it in target and on each node up the path (adjusting k accordingly and calling on right/left of that node, opposite where target is - as otherwise we\'d be coming back towards target!).\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\n  public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n    List<Integer> result = new ArrayList<>();\n    if (k == 0) {\n      result.add(target.val);\n      return result;\n    }\n    List<TreeNode> rootToTarget = new ArrayList<>();\n    rootToTarget.add(root);\n    getPath(root, target, rootToTarget);\n    distanceK(target, k, result);\n    for (int i = rootToTarget.size() - 2; i >= 0; i--) {\n      k--;\n      TreeNode parent = rootToTarget.get(i);\n      if (k == 0) {\n        result.add(parent.val);\n        break;\n      }\n      TreeNode child = rootToTarget.get(i + 1);\n      if (child == parent.right) {\n        distanceK(parent.left, k - 1, result);\n      } else {\n        // child == parent.left\n        distanceK(parent.right, k - 1, result);\n      }\n    }\n    return result;\n  }\n\n  private void distanceK(TreeNode node, int k, List<Integer> result) {\n    if (node == null) {\n      return;\n    }\n    if (k == 0) {\n      result.add(node.val);\n      return;\n    }\n    distanceK(node.left, k - 1, result);\n    distanceK(node.right, k - 1, result);\n  }\n\n  private boolean getPath(TreeNode node, TreeNode target, List<TreeNode> rootToTarget) {\n    if (node == null) {\n      return false;\n    }\n    if (node == target) {\n      return true;\n    }\n    rootToTarget.add(node.left);\n    if (getPath(node.left, target, rootToTarget)) {\n      return true;\n    }\n    rootToTarget.remove(rootToTarget.size() - 1);\n    rootToTarget.add(node.right);\n    if (getPath(node.right, target, rootToTarget)) {\n      return true;\n    }\n    rootToTarget.remove(rootToTarget.size() - 1);\n    return false;\n  }\n}\n```\n\nVOTE UP if it helped! \u2727\u207A\u2E1C(\u25CF\u02D9\u25BE\u02D9\u25CF)\u2E1D\u207A\u2727\n\n\n![NVIDIA GeForce Overlay DT-2023-06-24 18_54_15.png](https://assets.leetcode.com/users/images/d6627f7e-2523-4fd1-9a4a-f3691c49b665_1687629508.5846446.png)\n\n![1bfcf29e-98b3-4ab4-9718-c05e4f200b8e_1682534142.8088818\\[1\\].jpeg](https://assets.leetcode.com/users/images/8239d74e-4d1e-4449-9f9f-d3a4caa12565_1687629609.2291625.jpeg)\n\n
['Recursion', 'Java']