二叉树中的链表 图解题解

这道题到底在问什么

输入

head=[40,20,80], root 见演示树

输出

true(右边 40 → 20 → 80 走通)

输入

head=[40,20,80,90], root 同上

输出

false(80 后面再没有 90)

最优解：一步一步想明白

1. 3记牢两层:外层换起点,内层从起点一路向下比链表。链表先走完就赢;遇到空节点或值对不上就断,回头换方向。下面每一帧都在套这条规则。
2. 4head 链表三个值 40,20,80 待在树里找一条向下路先看清两边。左边是树:根是 10,它有两个孩子都是 40;左边那个 40 下面挂 20 和 70,20 再下面挂一个 30;右边那个 40 下面挂 20 和 90,这个 20 下面挂一个 80。右边面板是链表 40 → 20 → 80。我们的任务,就是在树里找一条一直向下的路,值正好按 40、20、80 排下来。
3. 5路径只能父亲走到孩子,不能拐弯不能向上强调一个容易忽略的点:路径必须一直向下。也就是从某个节点出发,只能顺着父亲到孩子的方向走,不能拐到兄弟,也不能往上回。所以第一步要解决的是:链表的第一个值 40,该从树里哪个节点开始接?那就把每个节点都当起点试一遍。
4. 6拿链表第一个值 40 和根 10 比从根 10 开始试。链表当前要匹配的是第一个值 40,那就拿它和起点 10 比。规则很直接:起点的值必须等于链表第一个值 40,这条路才有戏。来看 10 和 40 相不相等。
5. 7根作起点第一步就断,换起点10 不等于 40,第一步就对不上。既然起点的值都和链表头不一样,这条根本接不起来,直接断掉。外层于是放弃用根当起点,转头去它的孩子里继续找。先去左孩子那个 40。
6. 8换根的左孩子 40 当起点,比 40 与 40换根的左孩子,这个 40,当新起点。蓝色的根表示它已经试过、淘汰了。现在拿链表第一个值 40 和这个起点 40 比。这回看着有戏:40 和 40。
7. 9起点 40 命中,接下来比第二个值 2040 等于 40,第一格对上了!这个 40 标成匹配链的一员。链表往前走一格,接下来要匹配的是第二个值 20。按规则,要分别往这个 40 的左孩子和右孩子两个方向继续向下找 20。它的左孩子是 20,右孩子是 70,先看左边。
8. 10拿链表当前值 20 和节点 20 比走到这个 40 的左孩子,值是 20。链表现在要匹配的也正好是 20。拿它俩比:20 和 20,看起来又能对上。
9. 11两格对上,接下来找第三个值 8020 等于 20,第二格也对上了!现在匹配链已经是 40 → 20,链表只剩最后一个值 80 要找。继续往这个 20 的孩子走。它的左孩子是 30,右孩子是空。先看左孩子 30。
10. 12拿链表当前值 80 和节点 30 比走到这个 20 的左孩子,值是 30。链表现在要匹配的是最后一个值 80。拿 30 和 80 比,这俩差得有点远了。
11. 13左孩子这条断了30 不等于 80,对不上,这个方向断掉。但别急着否定整条路,这个 20 还有一个右孩子方向没试。来看它的右孩子。
12. 14另一个方向也接不上 80这个 20 的右孩子是空的。树节点都没有了,自然也接不上 80。两个方向都断了,说明从左边这个 40 出发、走到 20 这一支,到第三层就接不上 80 了。那就得往回退,回到那个 40,试它的另一条分支。
13. 15链表退回到第二个值 20,比 70 与 20回溯。退回到左边这个 40,它的左孩子那条已经走死,现在试它的右孩子 70。注意链表也跟着退回去:之前在 20 那一格走断了,现在重新从 40 之后的第二个值 20 开始,拿它和 70 比。
14. 16左边 40 是最接近的一条,匹配两层仍断70 不等于 20,这条也断。到此,左边这个 40 当起点的所有向下方向都试完了,全军覆没。不过它是目前最接近的一条:成功接上了 40 和 20 两层,只差最后一个 80 没接上。可惜差一点也是不行。外层只好放弃这个 40,继续换别的节点当起点。
15. 1720,30,70 当起点,第一步就对不上 40外层会老老实实把每个节点都当起点试。但像 20、30、70 这些节点,链表第一个值要的是 40,它们第一步就对不上,试一下立刻就弃,花不了多少功夫。这些蓝色节点表示都淘汰了。真正还没试的关键起点,是根右边那个 40。
16. 18换根的右孩子 40 当起点,比 40 与 40轮到根的右孩子,这个 40。前面试过的节点都成蓝色了。和左边那个 40 一样,先拿链表第一个值 40 和它比。又是 40 对 40。
17. 19右边 40 命中,接下来比第二个值 2040 等于 40,第一格又对上,这个 40 进入匹配链。链表前进,要找第二个值 20。看这个 40 的两个孩子:左孩子是 20,右孩子是 90。先看左边的 20。
18. 20拿链表当前值 20 和节点 20 比走到右边 40 的左孩子,值是 20,链表要找的也是 20。拿它俩比,20 对 20。
19. 21两格对上,只剩最后一个 8020 等于 20,第二格对上!匹配链现在是 40 → 20,链表只剩最后一个 80。看这个 20 的孩子:左孩子正好是 80,右孩子是空。来看左孩子。
20. 22拿链表最后一个值 80 和节点 80 比走到这个 20 的左孩子,值是 80。链表最后要匹配的也正是 80。这是决定胜负的一比:80 和 80。
21. 23三个值全部对上,这条向下路径成立80 等于 80!链表的三个值 40、20、80 全部按顺序对上了。匹配到这里,链表已经走完,后面再没有节点要找了,这正是成功的标志:链表先走完,就说明这条向下的路径完整地装下了整条链表。返回 true。
22. 24路径 40 → 20 → 80 在右子树走通收工。绿色的三个节点 40 → 20 → 80,就是树里那条和链表一一对上的向下路径,它在根右边那个 40 的底下。因为找到了这样一条路径,整道题的答案就是 true。
23. 25左边 40 匹配两层断,右边 40 走通最后回放一下最有意思的对比。树里有两个 40,左边那个红色的,匹配上了 40 和 20,可第三层接不上 80,断了;右边那个绿色的,一路 40、20、80 顺顺当当走到底。这正说明:同样的起点值,结果可能完全不同,所以外层要不厌其烦地把每个节点都试一遍,只要有任意一条向下路径成立,答案就是 true。

⚠️ 容易写错的地方

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

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        def dfs(head, root):
            if head is None:
                return True
            if root is None or root.val != head.val:
                return False
            return dfs(head.next, root.left) or dfs(head.next, root.right)

        if root is None:
            return False
        return (
            dfs(head, root)
            or self.isSubPath(head, root.left)
            or self.isSubPath(head, root.right)
        )

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#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 *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) {
            return false;
        }
        return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }

    bool dfs(ListNode* head, TreeNode* root) {
        if (!head) {
            return true;
        }
        if (!root || head->val != root->val) {
            return false;
        }
        return dfs(head->next, root->left) || dfs(head->next, root->right);
    }
};

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode 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 TreeNode { int val; TreeNode left; TreeNode 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (root == null) {
            return false;
        }
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) {
            return true;
        }
        if (root == null || head.val != root.val) {
            return false;
        }
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }
}

复杂度

面试官可能追问