[LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

• The number of nodes in the tree will be in the range [1, 2500].
• The number of nodes in the list will be in the range [1, 100].
• 1 <= Node.val <= 100 for each node in the linked list and binary tree.

这道题说是给了一棵二叉树，还给了一个链表，问能不能在二叉树中找到一条路径 path，使得其正好是给定的结点链表，题目中例子中的图很好的解释了题意。这里的二叉树的路径并没有限制要从根节点开始，结束位置也不一定要是叶结点，那么理论上不同路径的数量就太多了。如果是想先求出二叉树的所有路径后，再来跟结点链表比较的话，一是太麻烦了，二是效率也不高。最好的办法还是在遍历的过程中就直接开始比较了，比较的方法就是当遇到和此时链表头结点相同的结点时，开始进行下一个结点的比较，由于路径可以去左子结点或者右子结点，所以左右子结点都要去尝试，这里用递归就非常合适了，只要左右子结点任意一个返回 true 了，那么就说明成功匹配了。如果当前的结点和链表头结点的值不相同的话，则分别再去左右子结点进行尝试，此时左右子结点还是跟原来的链表首结点去比较，因为之前没有匹配上，同样，只要左右子结点的递归任意一个返回 true 了，就说明成功匹配上了。根据这种思路写出的代码如下（注意这种下面这种解法是错误的，之后会分析）：

// Wrong Solution
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!head) return true;
        if (!root) return false;
        if (head->val == root->val) {
            return isSubPath(head->next, root->left) || isSubPath(head->next, root->right);
        }
        return isSubPath(head, root->left) || isSubPath(head, root->right);
    }
};

上面的解法虽然简洁，但实际上是错误的解法，这里可以举一个反例：head = [4,2,2], root = [4,2,null,4,null,2]，二叉树的结构如下所示：

      4
     /
    2
   /
  4
 /
2

上面解法错误的原因是当 head 匹配完4和2之后，下一个2匹配不上了，因为二叉树中是4，但此时却没有从开头的4重新匹配，而是继续匹配链表中剩下的那个2，这样在跳过二叉树中的第二个4之后，最后一个2就匹配上了，整个就返回了 true。但实际上是错误的，给定的二叉树中并没有一个连续的 4->2->2 路径，相当于找到了类似于字符串中的子序列，而要求的却是子串。正确的做法实际上是对每个结点都当做起始点来匹配一下，这里用一个子函数 dfs 来匹配，匹配的方法就是看链表和二叉树的当前结点值是否相等，是的话再对左右子结点调用递归，只要任意一个返回 true 就行了。在主函数中，调用完 dfs 后，还要分别对左右子结点调用主函数的递归，这样才能保证把每个结点都当起始点来匹配，才能避免上面那个反例的情况，参见代码如下：

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!head) return true;
        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) return false;
        return head->val == root->val && (dfs(head->next, root->left) || dfs(head->next, root->right));
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1367

参考资料：

https://leetcode.com/problems/linked-list-in-binary-tree

https://leetcode.com/problems/linked-list-in-binary-tree/solutions/524881/python-recursive-solution-o-n-l-time/

https://leetcode.com/problems/linked-list-in-binary-tree/solutions/524821/c-simple-recursion/

LeetCode All in One 题目讲解汇总(持续更新中...)