1367.二叉树中的链表

链接：LeetCode1367.二叉树中的链表

错误分析

其实这道题目思路很简单：
采用前序遍历的方式从根节点开始遍历二叉树，并在遍历的过程中比较与链表节点的值是否相等，如果当前链表节点的值和树节点的值相等，就在树节点的左右子树寻找下一个链表节点；如果不相等就在树节点的左右子树寻找当前链表节点的值；以下是根据这个思想写出的第一版代码：

/*** 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) {return backtracking(head,root);}
private:bool backtracking(ListNode*head,TreeNode *root){if(!head) return true;if(!root) return false;if(root->val==head->val){head=head->next;}if(backtracking(head,root->left)) return true;return backtracking(head,root->right);}
};

这个代码只能通过61/67的测试案例

其实我一开始检查代码的时候并没有发现有什么错误，感觉很符合逻辑，实在不明白哪里出错了。
后来我发现，我传递的参数是以指针的形式传递的，如果当前的链表节点的值与树节点的值相等，会做这么一个操作

if(head->val==root->val) head=head->next;

然后再将这个head传递给下一次递归，这个过程无意当中修改了链表中节点的指向，也就是无意中修改了链表的结构，所以针对某些案例得到了错误的答案。

后来我再次回想这版错误答案的时候，我发现错误之处并非像上述所说的那样，链表的结构不会因为传递的参数而被改变，就像遍历二叉树的时候，树的结构不会因为传递的参数而发生变化。

错误之处应该是：举个例子来说
假设链表的结构为4，2，1；树中包含链表路径的一个分支结构为4，2，8；当head指向1并且root指向8的时候，1！=8，此时会执行以下代码

  if(backtracking(head,root->left)) return true;

这行代码的意思就是，在root[8]的左子树寻找以head[1]为头结点的链表，这个操作把链表进行了分割，所以导致结果错误。

正确解答

为了避免上述的错误，应该在遇到链表节点的值和当前树节点的值不相等的时候，就立马返回false。
在isSubPath()这个函数中，重新用树节点的左右子树与链表头结点进行匹配

/*** 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(!head) return true;if(!root) return false;//这个isSubPath之所以出现在||的后面是因为要找到当一个与head头匹配的root节点从当前位置开始向下寻找return backtracking(head,root) ||isSubPath(head,root->left)||isSubPath(head,root->right);}
private:bool backtracking(ListNode*head,TreeNode *root){if(!head) return true;if(!root) return false;if(root->val!=head->val) return false;return backtracking(head->next,root->left) || backtracking(head->next,root->right);}
};