LeetCode 863中等树/图BFS

二叉树中距离为 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]
输入: target=1, k=1
输出: [0,8,3]

最优解：一步一步想明白

3记住「先给每个节点记住父亲、把树变无向图,再从 target 一圈圈 BFS 扩 k 层」,下面逐帧套它。
4先看清局面:目标节点是 5(紫色高亮),我们要找所有离它恰好 2 步的节点。难点是 5 的上方(父亲 3 那一支)也算邻居,可树指针只能往下。
5第一步建父指针。DFS 走一遍:5 和 1 的父亲都是 3,记进哈希表。有了父指针,5 就能反过来走到 3。
6继续记:6、2 的父亲是 5,0、8 的父亲是 1,7、4 的父亲是 2;根 3 没有父亲。到此每条边都能双向走了,这棵树就成了一张无向图。
7有了父指针,从任何节点都能往「左孩子、右孩子、父亲」三个方向走。接下来从 target 5 出发做 BFS,像水波一圈圈扩散,第 2 圈就是答案。
8把 target 5 放进队列,距离记 0,并标进 seen。5 自己离自己 0 步,从它开始一圈圈往外扩。
9现在从距离 0 的这一圈 5(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 1 的下一圈。
10从距离 0 的 5 看它的左孩子 6:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6。
11从距离 0 的 5 看它的右孩子 2:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2。
12从距离 0 的 5 看它的父亲 3:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2、3。
13距离 0 的节点全扩散完了。离 target 恰好 1 步的是 6、2、3。还没到 k=2,继续从它们往外扩。
14现在从距离 1 的这一圈 6、2、3(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 2 的下一圈。
15从距离 1 的 6 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
16从距离 1 的 2 看它的左孩子 7:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7。
17从距离 1 的 2 看它的右孩子 4:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4。
18从距离 1 的 2 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
19从距离 1 的 3 看它的左孩子 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
20从距离 1 的 3 看它的右孩子 1:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4、1。
21距离 1 的节点全扩散完了。离 target 恰好 2 步的是 7、4、1。正好扩满 2 圈,这一圈就是要找的答案。
22扩满 2 圈,队列里剩下的 7、4、1(紫色)就是距 target 5 恰好 2 步的全部节点,答案 [7, 4, 1]。7、4 在 5 下方经过 2,1 在上方经过 3,都是两步。
23回头看整趟:先 DFS 给每个节点记父亲、把树变成无向图,再从 target 一圈圈 BFS、靠 seen 防回头,扩满 k 圈就拿到答案。每个节点最多进出队一次,时间 O(n)。

⚠️ 容易写错的地方

✗ 错：只往子树找、忘了往上走

✓ 对：建父指针,把树当无向图、三方向都走

距 target k 步的节点可能在父亲那一支,只往下会漏掉(如本例的 1)

✗ 错：BFS 不记 seen

✓ 对：每个节点入队即标 seen,已访问的跳过

无向图里会沿父子边来回走,不去重会死循环、距离也算错

✗ 错：扩散圈数搞错(多扩或少扩一圈)

✓ 对：恰好循环 k 次,结束时队列即答案

多扩一圈得到的是距离 k+1 的节点,少一圈是 k−1,差一步全错

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parent={}
        def dfs(n,p=None):
            if n:
                parent[n]=p; dfs(n.left,n); dfs(n.right,n)
        dfs(root)
        q=[target]; seen={target}
        for _ in range(k):
            nq=[]
            for n in q:
                for x in (n.left,n.right,parent[n]):
                    if x and x not in seen: seen.add(x); nq.append(x)
            q=nq
        return [n.val for n in q]

C++

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<int> distanceK(TreeNode* root,TreeNode* target,int k){ unordered_map<TreeNode*,TreeNode*> par; function<void(TreeNode*,TreeNode*)> dfs=[&](TreeNode*n,TreeNode*p){ if(!n)return; par[n]=p; dfs(n->left,n); dfs(n->right,n);}; dfs(root,nullptr); queue<TreeNode*> q; unordered_set<TreeNode*> seen; q.push(target); seen.insert(target); while(k--){ for(int sz=q.size();sz--;){ auto n=q.front(); q.pop(); for(auto x:{n->left,n->right,par[n]}) if(x&&!seen.count(x)){seen.insert(x); q.push(x);} } } vector<int> ans; while(!q.empty()){ans.push_back(q.front()->val); q.pop();} return ans; }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public List<Integer> distanceK(TreeNode root,TreeNode target,int k){ Map<TreeNode,TreeNode> par=new HashMap<>(); dfs(root,null,par); Queue<TreeNode> q=new ArrayDeque<>(); Set<TreeNode> seen=new HashSet<>(); q.offer(target); seen.add(target); while(k-->0){ for(int sz=q.size();sz>0;sz--){ TreeNode n=q.poll(); for(TreeNode x:new TreeNode[]{n.left,n.right,par.get(n)}) if(x!=null&&seen.add(x)) q.offer(x); } } ArrayList<Integer> ans=new ArrayList<>(); while(!q.isEmpty())ans.add(q.poll().val); return ans;} void dfs(TreeNode n,TreeNode p,Map<TreeNode,TreeNode> par){ if(n==null)return; par.put(n,p); dfs(n.left,n,par); dfs(n.right,n,par);} }

复杂度

时间

O(n)

DFS 建父指针遍历每个节点一次;BFS 中每个节点最多进出队一次,n 是节点总数

空间

O(n)

parent 哈希表、seen 集合、队列各最多装 O(n) 个节点;递归栈最坏 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着二叉树中距离为 K 的节点的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

除了建父指针 + BFS,还有别的做法吗?+

有。一种是 DFS:先找到从根到 target 的路径,再对 target 的子树按深度找距离 k 的节点;同时处理 target 的各级祖先,设祖先 a 距 target 为 d:若 d 恰好等于 k,祖先 a 自己就是一个答案;若 d 小于 k,就在 a 的「另一侧子树」里找距离 k−d−1 的节点。逻辑更绕、容易写错。建父指针 + BFS 直观很多,是面试首选。

如果要求返回的是节点而不是值,或者 k 很大怎么办?+

返回节点只需把最后队列里的节点直接收集即可,逻辑不变。k 很大时,BFS 会在某一圈扩不出新节点、队列变空,直接返回空列表,不会有额外开销;整体仍是 O(n)。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把二叉树中距离为 K 的节点一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 863中等树/图BFS

二叉树中距离为 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]
输入: target=1, k=1
输出: [0,8,3]

最优解：一步一步想明白

3记住「先给每个节点记住父亲、把树变无向图,再从 target 一圈圈 BFS 扩 k 层」,下面逐帧套它。
4先看清局面:目标节点是 5(紫色高亮),我们要找所有离它恰好 2 步的节点。难点是 5 的上方(父亲 3 那一支)也算邻居,可树指针只能往下。
5第一步建父指针。DFS 走一遍:5 和 1 的父亲都是 3,记进哈希表。有了父指针,5 就能反过来走到 3。
6继续记:6、2 的父亲是 5,0、8 的父亲是 1,7、4 的父亲是 2;根 3 没有父亲。到此每条边都能双向走了,这棵树就成了一张无向图。
7有了父指针,从任何节点都能往「左孩子、右孩子、父亲」三个方向走。接下来从 target 5 出发做 BFS,像水波一圈圈扩散,第 2 圈就是答案。
8把 target 5 放进队列,距离记 0,并标进 seen。5 自己离自己 0 步,从它开始一圈圈往外扩。
9现在从距离 0 的这一圈 5(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 1 的下一圈。
10从距离 0 的 5 看它的左孩子 6:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6。
11从距离 0 的 5 看它的右孩子 2:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2。
12从距离 0 的 5 看它的父亲 3:没访问过,入队、标进 seen,它离 target 是 1 步。下一圈现在是 6、2、3。
13距离 0 的节点全扩散完了。离 target 恰好 1 步的是 6、2、3。还没到 k=2,继续从它们往外扩。
14现在从距离 1 的这一圈 6、2、3(紫色)出发,逐个朝三个方向看邻居,把新节点收进距离 2 的下一圈。
15从距离 1 的 6 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
16从距离 1 的 2 看它的左孩子 7:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7。
17从距离 1 的 2 看它的右孩子 4:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4。
18从距离 1 的 2 看它的父亲 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
19从距离 1 的 3 看它的左孩子 5(红色):5 已经访问过(在 seen 里),跳过,不能往回走。
20从距离 1 的 3 看它的右孩子 1:没访问过,入队、标进 seen,它离 target 是 2 步。下一圈现在是 7、4、1。
21距离 1 的节点全扩散完了。离 target 恰好 2 步的是 7、4、1。正好扩满 2 圈,这一圈就是要找的答案。
22扩满 2 圈,队列里剩下的 7、4、1(紫色)就是距 target 5 恰好 2 步的全部节点,答案 [7, 4, 1]。7、4 在 5 下方经过 2,1 在上方经过 3,都是两步。
23回头看整趟:先 DFS 给每个节点记父亲、把树变成无向图,再从 target 一圈圈 BFS、靠 seen 防回头,扩满 k 圈就拿到答案。每个节点最多进出队一次,时间 O(n)。

⚠️ 容易写错的地方

✗ 错：只往子树找、忘了往上走

✓ 对：建父指针,把树当无向图、三方向都走

距 target k 步的节点可能在父亲那一支,只往下会漏掉(如本例的 1)

✗ 错：BFS 不记 seen

✓ 对：每个节点入队即标 seen,已访问的跳过

无向图里会沿父子边来回走,不去重会死循环、距离也算错

✗ 错：扩散圈数搞错(多扩或少扩一圈)

✓ 对：恰好循环 k 次,结束时队列即答案

多扩一圈得到的是距离 k+1 的节点,少一圈是 k−1,差一步全错

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parent={}
        def dfs(n,p=None):
            if n:
                parent[n]=p; dfs(n.left,n); dfs(n.right,n)
        dfs(root)
        q=[target]; seen={target}
        for _ in range(k):
            nq=[]
            for n in q:
                for x in (n.left,n.right,parent[n]):
                    if x and x not in seen: seen.add(x); nq.append(x)
            q=nq
        return [n.val for n in q]

C++

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<int> distanceK(TreeNode* root,TreeNode* target,int k){ unordered_map<TreeNode*,TreeNode*> par; function<void(TreeNode*,TreeNode*)> dfs=[&](TreeNode*n,TreeNode*p){ if(!n)return; par[n]=p; dfs(n->left,n); dfs(n->right,n);}; dfs(root,nullptr); queue<TreeNode*> q; unordered_set<TreeNode*> seen; q.push(target); seen.insert(target); while(k--){ for(int sz=q.size();sz--;){ auto n=q.front(); q.pop(); for(auto x:{n->left,n->right,par[n]}) if(x&&!seen.count(x)){seen.insert(x); q.push(x);} } } vector<int> ans; while(!q.empty()){ans.push_back(q.front()->val); q.pop();} return ans; }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public List<Integer> distanceK(TreeNode root,TreeNode target,int k){ Map<TreeNode,TreeNode> par=new HashMap<>(); dfs(root,null,par); Queue<TreeNode> q=new ArrayDeque<>(); Set<TreeNode> seen=new HashSet<>(); q.offer(target); seen.add(target); while(k-->0){ for(int sz=q.size();sz>0;sz--){ TreeNode n=q.poll(); for(TreeNode x:new TreeNode[]{n.left,n.right,par.get(n)}) if(x!=null&&seen.add(x)) q.offer(x); } } ArrayList<Integer> ans=new ArrayList<>(); while(!q.isEmpty())ans.add(q.poll().val); return ans;} void dfs(TreeNode n,TreeNode p,Map<TreeNode,TreeNode> par){ if(n==null)return; par.put(n,p); dfs(n.left,n,par); dfs(n.right,n,par);} }

复杂度

时间

O(n)

DFS 建父指针遍历每个节点一次;BFS 中每个节点最多进出队一次,n 是节点总数

空间

O(n)

parent 哈希表、seen 集合、队列各最多装 O(n) 个节点;递归栈最坏 O(n)

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

除了建父指针 + BFS,还有别的做法吗?+

如果要求返回的是节点而不是值,或者 k 很大怎么办?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

二叉树中距离为 K 的节点 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

二叉树中距离为 K 的节点 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

二叉树中距离为 K 的节点图解题解

二叉树中距离为 K 的节点图解题解