二叉树中的列表（双递归）
问题：
思路：
设计一判断匹配的递归函数，其功能为判断以当前节点为起点往下的路径是否有与链表相匹配的，有四种情况：
1.当前链表节点为空，说明匹配成功，返回TRUE
2.当前树中节点为空，匹配失败，返回FALSE
3.树中节点值不等于链表中节点，返回FALSE
4.若不是上述三种情况，则成功匹配了一部分链表节点，继续在根的左子树以及右子树（若左子树中不能匹配，则还需在右子树中进行匹配）中调用递归函数进行判断
接下来只需从根节点开始逐个调用匹配函数进行判断即可，因此设计一前序遍历的递归函数
首先对根节点调用匹配函数，若返回FALSE，则再对左子树以及右子树进行判断
代码：
/**
* 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 Preorder( ListNode* head,TreeNode* root )
{
if( head==NULL )
return true;
else if( root==NULL )
return false;
else if( root->val!=head->val )
return false;
return Preorder( head->next,root->left ) || Preorder( head->next,root->right );
}
bool isSubPath(ListNode* head, TreeNode* root) {
if( root==NULL )
return false;
return Preorder( head,root ) || isSubPath( head,root->left ) || isSubPath( head,root->right );
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153827.html
