# LeetCode 863. All Nodes Distance K in Binary Tree

 关注
发布于: 2020 年 06 月 01 日
# LeetCode 863. All Nodes Distance K in Binary Tree
@(LeetCode)
问题描述﻿
给定一颗二叉树的根节点 root，目标节点 target，和一个整数 K。
返回与目标节点距离为 K 的节点列表，顺序随意。
﻿
栗 1：
﻿
﻿
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
﻿
解释：
﻿
树的结构如上图所示。与节点 5 的距离为 2 的节点有：7、4、1。
﻿
注意：
二叉树非空。
每个节点值都是唯一的，范围在 [0, 500]。
target 节点在树中。
0 <= K <= 1000。
﻿
想看英文原文的戳这里。
﻿
解题思路解法 1﻿
解法 1 也是我自己的解法。
﻿
初看这题，我冒出的想法是：计算目标节点所在的层，然后再往下数 K 层，则该层上的所有节点与其距离肯定为 K。
﻿
但是，又回头看了看栗子，发现没那么简单。其不仅仅包括目标节点的子节点 7、4，而且还包括其兄弟节点 1，也可认为是其父节点的子节点。
﻿
栗子分析﻿
先看一个复杂些的栗子，树结构如下图所示。其中 K = 3，红色代表目标节点 5。
﻿
﻿
我们从图中可以看出，与其距离为 3 的节点包括 8、3。下图中用浅绿色标出，黄色代表其祖先节点。
﻿
﻿
下面，我们来分析一下节点  8、3 怎么得来的。
﻿
节点 8 ：其父节点 2 与目标节点 5 的距离为 1，因此只需要往左边分支找到与节点 2 距离为 2 的节点。
节点 3：其父节点 1 与目标节点 5 的距离为 2，因此只需要往右边分支上找到与节点 1 距离为 1 的节点。
﻿
思路梳理﻿
通过对栗子结果进行分析，我们可以确定节点的寻找方向：
目标节点的子节点，往下找。
目标节点所有祖先节点的子节点。先往上找到祖先节点后，再找各祖先节点的子树，即往下找。
﻿
如何找到目标节点的祖先节点？简单，只需要计算出从根节点到目标节点的路径，记录下来。
﻿
计算出其祖先节点后，怎样找到与其距离为 K 的节点呢？
﻿
直接父节点，记为 p1。
  
  1. 如果目标节点是 p1 的左子树，那么只需要从 p1 的右节点开始遍历，找到与右节点距离为 K - 2 的所有节点；
﻿
  2. 如果目标节点是 p1 的右子树，那么只需要从 p1 的左节点开始遍历，找到与左节点距离为 K - 2 的所有节点。
﻿
	也就是说，从父节点的另一个子树开始找起。这就需要我们在计算路径的时候，记下节点方向，是左还是右节点。
﻿
	为什么是 K -2 ？因为父节点与目标节点距离为 1，父节点与另一方向子节点距离也为 1。
﻿
	这样就全部转换为向下查找：求从某节点开始，与其距离为 K-2 的所有子节点集合。而这种查找方式比较简单。
﻿
倒数第二个父节点，记为 p2。
﻿
 推论同上，只不过距离为 K - 3。
 
 ... 
 
以此类推。
﻿
很显然，这需要知道祖先节点与目标节点的距离。
﻿
而当我们以数组记录节点路径时（不包括目标节点），自然可以得出某节点与目标节点的距离。
﻿
比如路径为 paths = [A, B, C]。则 A 与目标节点的距离为 paths.length，C 与其距离为 paths.length - 1，B 与其距离为 paths.length - 2。
﻿
以上我们只是计算了以父节点另一分支开始的情况，而从它自身开始的节点也需要考虑。
﻿
从上述的分析中，将所要做的步骤分解如下：
计算从根节点到目标节点路径，并记录各个节点方向。
依次遍历各祖先节点，计算出以另一子节点开始，距离为 n 的所有节点，n  跟祖先节点位置有关。注意如果某父节点与其距离刚好是 K，则不需要计算子节点了。
计算以目标节点开始，与其距离为 K 的节点。
﻿
这样，就可求出所有距离为 K 的节点。
﻿
代码实现﻿
下面给出关键性代码。
﻿
寻找节点路径。
﻿
// 找到 root -> target 之间的路径，不包括 target
var getPath = function (root, target) {
    if (root) {
        if (root == target) {
            return []
        } else {
            let result1 = null
            let result2 = null
﻿
            // 左边是否存在节点
            if (root.left) {
                result1 = getPath(root.left, target)
            }
            
            // 右边是否存在节点
            if (root.right) {
                result2 = getPath(root.right, target)
            }
﻿
            if (result1) {
                // 0 代表左边节点
                const curNode = { node: root, dir: 0 }
                return [curNode].concat(result1)
            } else if (result2) {
                // 1 代表右边节点
                const curNode = { node: root, dir: 1 }
                return [curNode].concat(result2)
            }
﻿
            // 都不存在
            return null
        }
    }
﻿
    return null
}
﻿
找出以某节点开始的，距离为 n 的所有节点。
﻿
// 以 node 开始的，长度为 totalDistance 的节点
var distance = function (node, curDistance, totalDistance) {
﻿
    console.log(node.val, curDistance, totalDistance)
    if (node) {
        if (curDistance === totalDistance) {
            return [node.val]
        }
﻿
        let result = []
        if (node.left) {
            const leftResult = distance(node.left, curDistance + 1, totalDistance)
            result = result.concat(leftResult)
        }
﻿
        if (node.right) {
            const rightResult = distance(node.right, curDistance + 1, totalDistance)
            result = result.concat(rightResult)
        }        
﻿
        return result
    }
﻿
    return []
}
﻿
完整代码可点此查看。
﻿
解法 2﻿
这种解法的思路在大体上差不多，但是没解法 1 那么复杂，因为它只需记录路径上的节点（包括目标节点）与目标节点的距离。
思路梳理﻿
主要思路如下：
计算出路径上的节点与目标节点的距离。
计算树中每个节点与目标节点的距离，如果等于 K，则满足条件。  
由于之前计算出了路径上节点的距离，可以直接获取。而往子节点遍历时只需要在其基础上 +1 即可。
﻿
可见思路之清晰，当看完代码后，会发现实现也很简洁。
结合栗子分析﻿
以解法 1 中的栗子来看，路径上的节点 [1, 2, 5] 与目标节点距离的数据如下：
﻿
// 节点 2 与节点 5 的距离为 1
Key = 2, Value = 1
﻿
// 节点 5，与其自身距离为 0
Key = 5, Value = 0
﻿
// 节点 1 与节点 5 的距离为 2
Key = 1, Value = 2
﻿
树中每个节点与目标节点 6 的距离如下：
节点 1: 2
节点 2: 1
节点 4: 2
节点 8: 3
节点 5: 0
节点 9: 1
节点 3: 3
节点 6: 4
节点 7: 4
﻿
其中 1、2、5 为路径上的节点，可以看到更新为了正确的值。这就是从已计算的结果中取值。
代码实现﻿
关键代码如下：
private void dfs(TreeNode root, int K, int length, List<Integer> res) {
    if (root == null) return;
﻿
    int tmp = length;
﻿
    // 如果已记录，则使用已有值。很关键，特别是对于同分支方向的查找
    if (map.containsKey(root)) tmp = map.get(root);
﻿
	// 距离满足
    if (tmp == K) res.add(root.val);
﻿
	// 遍历子树，距离 + 1
    dfs(root.left, K, tmp + 1, res);
    dfs(root.right, K, tmp + 1, res);
}
﻿
完整代码可点此查看。
﻿
通过对比两种解法，发现我的思路还是局限了些，老想着往祖先节点的另一分支上去找，所以才会需要记录节点的方向。而它这种方式，即使在祖先节点相同的分支找，根据已记录的节点距离，也会获取到与目标节点的真正距离，完全无需担心。
﻿