1367

二叉树数据结构如下

//definition of binary tree node struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

本题需要注意一点是子节点的匹配结果是受到父节点匹配结果影响的。分为两种情况：父节点匹配成功、父节点匹配失败 父节点匹配成功的情况

tree空tree不空list空truetruelist不空false继续匹配

父节点匹配失败的情况

tree空tree不空list空falsefalselist不空false继续匹配

所以只用一个递归函数是无法实现的。首先是单个节点的匹配，一个深度优先遍历

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

是否匹配成功需要结合单个节点的匹配和后续子树的匹配情况

bool isSubPath(ListNode* head, TreeNode* root) { //需要判断root是否是null，否则无法调用root->left,root->right if (root == nullptr) return false; return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right); }