二叉树中所有距离为K的节点

题目：给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出：[7,4,1]

解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1

image

var distanceK = function(root, target, k) {
    if (!root) return [];
    let res = [], paths = [], targetNode = null;
    function dfs(_root, _target) {
        if (!_root || targetNode) return;
        if (_root.val === _target.val) {
            targetNode = _root
        }
        if (_root.left) {
            _root.left.parent = _root;
            dfs(_root.left, target)
        }
        if (_root.right) {
            _root.right.parent = _root;
            dfs(_root.right, target)
        }
    }

    function getdownDis(node, k) {
        if(node === null || paths.indexOf(node) !== -1) return;
        paths.push(node);
        if(k > 0){
            getdownDis(node.left, k-1);
            getdownDis(node.right, k-1);  
        }else if(k === 0){
            res.push(node.val);
        }
    }
    // 找到target节点
    dfs(root, target)
    // 从当前节点向下寻找
    getdownDis(targetNode, k);
    // 从当前节点向上寻找
    while(targetNode.parent && k > 0){
        targetNode = targetNode.parent;
        getdownDis(targetNode, --k);
    }
    return res;
};