1367二叉树中的链表

下面是题目

下面是题目给出的代码模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        
    }
};

这种题目一般都有极其极其复杂的数据，所以递归是跑不了了

这是第一种解法，利用dfs来判断

/*
	首先，isSubPath是主函数，主函数的作用就是判断整树是否符合条件
	isSUb是判断函数，也会自身调用判断，用来判断这个树的根节点是否符合条件（可能是子树的根节点）
	
	因为树有很多分叉点，所以我们在没找到是否存在之前需要把所有的节点都判断一遍
	 return isSub(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);的作用就在于此，
	 我照着思路写的时候，一开始写的是isSub(head,root->left)||isSub(head,root->right)
	 这样是会报错的，因为这样只判断的这棵树的头节点和他的左右孩子节点，等于只判断了3个节点
	 但是我们题目中存在的情况可能是孩子结点的孩子节点是链表的头节点，这时候就出错了
	 所以我们要写isSubPath,这是判断整个子树的函数
	 
*/

class Solution {
public:
    bool isSub(ListNode *head,TreeNode *node)
    {
        //如果头节点为空，说明链表已经遍历完成，可以return true
        if(head==NULL)
            return true;
        //如果node为空，那么说明这颗树的根是空的，不构成判断条件，return false
        if(node==NULL)
            return false;
        //如果树根和链表val值不相等，从一开始就错了，那么这个节点就废了，return false
        if(head->val!=node->val)
            return false;
        //走到这一步，说明这个节点起码是符合的，所以我们要判断链表的下一个节点是否和这个树节点的左孩子或者右孩子相等
        return isSub(head->next,node->left)||isSub(head->next,node->right);
    }

    bool isSubPath(ListNode* head, TreeNode* root) {
        if(head== NULL)
            return true;
        if(root==NULL)
            return false;
        
       //这里要做 大树的根节点的判断，然后要做两棵子树的判断
        return isSub(head,root)||isSubPath(head,root->left)||isSubPath(head,root->right);
    }

};