上海网站建设公司 珍岛/百度网站排名关键词整站优化

二叉树与链表进行匹配

题目如下

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

解题思路

深度优先遍历搜索二叉树

• dfs函数用来判断树节点node开始，和链表节点head的匹配结果
• 在isSubPath函数中，如果dfs调用判断了当前节点不是的话，就递归去判断root节点的左右子树

解题代码及注释

#include<stdio.h>//dfs用来判断树节点node开始，和链表节点head的匹配结果。
bool dfs(TreeNode* rt, ListNode* head)
{//链表已经全部匹配完，匹配成功if (head == NULL)return true;//二叉树访问到了空节点，匹配失败if (rt == NULL)return false;//当前匹配的二叉树上节点的值与链表节点的值不相等，匹配失败if (rt->val != head->val)return false;return dfs(rt->left, head->next) || dfs(rt->right, head->next);
}
bool isSubPath(ListNode* head, TreeNode* root)
{if (root == NULL)return false;return dfs(root, head) || isSubPath(head, root->left) ||isSubPath(head, root->right);//dfs判断了当前节点如果不是的话,递归去判断root节点的左右子树。
}