313-二叉树与链表进行匹配

川长思鸟来 2023-01-22 11:52 4阅读 0赞

## 二叉树与链表进行匹配 ##

## 题目如下 ##

给你一棵以 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节点的左右子树。
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：二叉搜索树与双向链表

![44871f182802a0d7464f61f8de25bb1c.jpeg][] 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点

客官°小女子只卖身不卖艺/ 2024年04月06日 13:36/ 0 赞/ 69 阅读

相关二叉搜索树与双向链表

![ced485cbb11e458d81a746890b32cf3f.gif][] > 作者：敲代码の流川枫 > > 博客主页：[流川枫的博客][Link 1] > >

爱被打了一巴掌/ 2023年10月10日 15:07/ 0 赞/ 23 阅读

相关二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。遇树不决就递归 / struct Tre

た入场券/ 2023年02月17日 12:25/ 0 赞/ 30 阅读

相关 313-二叉树与链表进行匹配

二叉树与链表进行匹配题目如下给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰

川长思鸟来/ 2023年01月22日 11:52/ 0 赞/ 5 阅读

相关二叉搜索树与双向链表

\\题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路关于树的深度搜索操作，一般都

绝地灬酷狼/ 2022年10月28日 03:58/ 0 赞/ 189 阅读

相关二叉搜索树与双向链表

面试题27：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 void convertNode(Bi

「爱情、让人受尽委屈。」/ 2022年06月17日 07:08/ 0 赞/ 160 阅读

相关二叉树应用_二叉搜索树与双向链表

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点的指向。分析：由于要求转换之后的链表是排好序的，我们采用中序遍

短命女/ 2022年05月22日 03:06/ 0 赞/ 189 阅读

相关二叉树的二叉链表存储

/ c6-2.h 二叉树的二叉链表存储表示 / typedef struct BiTNode { TElemType data;

落日映苍穹つ/ 2022年03月31日 04:10/ 0 赞/ 300 阅读

相关二叉搜索树与双向链表

[二叉搜索树与双向链表][Link 1] 题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

清疚/ 2022年03月25日 15:37/ 0 赞/ 180 阅读

相关二叉搜索树与双向链表

时间限制：1秒空间限制：32768K 热度指数：210251 算法知识视频讲解题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建

悠悠/ 2022年03月09日 10:44/ 0 赞/ 205 阅读