cpp 解法, 执行用时: 8 ms, 内存消耗: 9 MB, 提交时间: 2022-12-04 11:28:52

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> result;
    TreeNode* ne;//存储目标节点的爸爸
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K)    {
        dfs(root, target, NULL); //首先把树分成两棵，一棵以目标节点为根，一棵以目标节点爸爸为根
        collect(target, 0, K); //搜索第一棵树深度为K的节点
        collect(ne, 0, K-1);//搜索第二棵树深度为K-1的节点
        return result;
    }
    bool dfs(TreeNode* root, TreeNode* target, TreeNode* father)
    {
        if(root == NULL)
        return 0;
        if(root == target) //如果搜到了目标节点，那么它爸爸就是新树的根
        {
            ne = father;
            return 1; //递归的时候返回：我们解除父子关系
        }
        if(dfs(root->left, target, root))//如果我成了左儿子的儿子，那我的爸爸就是我的新的左儿子
        {
            root->left = father;
            return 1;//递归的时候返回：我是你爸爸
        }
        if(dfs(root->right, target, root))//如果我成了我右儿子的儿子，那我的爸爸就是我的新的右儿子
        {
            root->right = father;
            return 1;//递归的时候返回：我是你爸爸
        }
        return 0;//递归的时候返回：爸爸
    }
    void collect(TreeNode* root, int n, int K) //搜索以K为根节点的树的第K层所有节点，随便拿DFS写的，这里也可以层序遍历
    {
        if(root == NULL)
        return;
        if(n == K)
        result.push_back(root->val);
        else
        {
            collect(root->left, n+1, K);
            collect(root->right, n+1, K);
        }
        return;
    }
};

java 解法, 执行用时: 9 ms, 内存消耗: 41.5 MB, 提交时间: 2022-12-04 11:27:56

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, TreeNode> parents = new HashMap<Integer, TreeNode>();
    List<Integer> ans = new ArrayList<Integer>();

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // 从 root 出发 DFS，记录每个结点的父结点
        findParents(root);

        // 从 target 出发 DFS，寻找所有深度为 k 的结点
        findAns(target, null, 0, k);

        return ans;
    }

    public void findParents(TreeNode node) {
        if (node.left != null) {
            parents.put(node.left.val, node);
            findParents(node.left);
        }
        if (node.right != null) {
            parents.put(node.right.val, node);
            findParents(node.right);
        }
    }

    public void findAns(TreeNode node, TreeNode from, int depth, int k) {
        if (node == null) {
            return;
        }
        if (depth == k) {
            ans.add(node.val);
            return;
        }
        if (node.left != from) {
            findAns(node.left, node, depth + 1, k);
        }
        if (node.right != from) {
            findAns(node.right, node, depth + 1, k);
        }
        if (parents.get(node.val) != from) {
            findAns(parents.get(node.val), node, depth + 1, k);
        }
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 3.2 MB, 提交时间: 2022-12-04 11:27:36

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distanceK(root, target *TreeNode, k int) (ans []int) {
    // 从 root 出发 DFS，记录每个结点的父结点
    parents := map[int]*TreeNode{}
    var findParents func(*TreeNode)
    findParents = func(node *TreeNode) {
        if node.Left != nil {
            parents[node.Left.Val] = node
            findParents(node.Left)
        }
        if node.Right != nil {
            parents[node.Right.Val] = node
            findParents(node.Right)
        }
    }
    findParents(root)

    // 从 target 出发 DFS，寻找所有深度为 k 的结点
    var findAns func(*TreeNode, *TreeNode, int)
    findAns = func(node, from *TreeNode, depth int) {
        if node == nil {
            return
        }
        if depth == k { // 将所有深度为 k 的结点的值计入结果
            ans = append(ans, node.Val)
            return
        }
        if node.Left != from {
            findAns(node.Left, node, depth+1)
        }
        if node.Right != from {
            findAns(node.Right, node, depth+1)
        }
        if parents[node.Val] != from {
            findAns(parents[node.Val], node, depth+1)
        }
    }
    findAns(target, nil, 0)
    return
}

javascript 解法, 执行用时: 84 ms, 内存消耗: 43.4 MB, 提交时间: 2022-12-04 11:27:16

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function(root, target, k) {
    const parents = new Map();
    const ans = [];

    const findParents = (node) => {
        if (node.left != null) {
            parents.set(node.left.val, node);
            findParents(node.left);
        }
        if (node.right != null) {
            parents.set(node.right.val, node);
            findParents(node.right);
        }
    }

    // 从 root 出发 DFS，记录每个结点的父结点
    findParents(root);

    const findAns = (node, from, depth, k) => {
        if (node == null) {
            return;
        }
        if (depth === k) {
            ans.push(node.val);
            return;
        }
        if (node.left !== from) {
            findAns(node.left, node, depth + 1, k);
        }
        if (node.right !== from) {
            findAns(node.right, node, depth + 1, k);
        }
        if (parents.get(node.val) !== from) {
            findAns(parents.get(node.val), node, depth + 1, k);
        }
    }
    // 从 target 出发 DFS，寻找所有深度为 k 的结点
    findAns(target, null, 0, k);

    return ans;
};