C语言重构【1367】二叉树中的列表

古城微笑少年丶 2022-11-11 14:53 113阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
    
    如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
    
    一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
    示例 1：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    输出：true
    解释：树中蓝色的节点构成了与链表对应的子路径。
    示例 2：

![在这里插入图片描述][20210321104436668.png]

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    输出：true
    示例 3：
    
    输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    输出：false
    解释：二叉树中不存在一一对应链表的路径。
    
    提示：
    
    二叉树和链表中的每个节点的值都满足 1 <= node.val <= 100 。
    链表包含的节点数目在 1 到 100 之间。
    二叉树包含的节点数目在 1 到 2500 之间。

#### 方案： ####

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution
    { 
    public:
        bool isSubPath(ListNode *head, TreeNode *root)
        { 
            return isSubPathHelp(head, root, true);
        }
        bool isSubPathHelp(ListNode *head, TreeNode *root, bool isRoot)
        { 
            //递归出口，head为空则代表走完了
            if (head == nullptr)
                return true;
            else if (root == nullptr)
                return false;
            //当前值匹配，往下找
            if (head->val == root->val)
            { 
                if (isSubPathHelp(head->next, root->left, false) || isSubPathHelp(head->next, root->right, false))
                    return true;
            }
            //当前值不匹配，但是呢，head是头，可以root向下再匹配
            if (isRoot == true)
                return isSubPathHelp(head, root->left, true) || isSubPathHelp(head, root->right, true);
            return false;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(nm):n=树的元素个数，m为链表的元素个数，理论上最大是要比较nm次的
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221022/86c7f6b2d1554e848bbcd114fb47bb91.png
[20210321104436668.png]: https://img-blog.csdnimg.cn/20210321104436668.png