Leetcode 1367. Linked List in Binary Tree (二叉树好题)

这篇具有很好参考价值的文章主要介绍了Leetcode 1367. Linked List in Binary Tree (二叉树好题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. Linked List in Binary Tree
    Medium
    Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.
Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.

解法1:
这题其实并不容易。要在整个二叉树里面,对每个节点调用helper()函数,用前中后序遍历应该都可以。helper()则是用的分解问题的方法。

/**
 * 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) {
        if (!head) return true;
        if (!root) return false;
        if (helper(head, root)) return true;
        return isSubPath(head, root->left) || isSubPath(head, root->right);  
    }
private:
    bool helper(ListNode* head, TreeNode* root) {
        if (!head) return true;
        if (!root) return false;
        if (head->val != root->val) return false;
        return helper(head->next, root->left) || helper(head->next, root->right);
    }
};

我一开始写成下面这样,但是不对。因为它只调用了一次helper(),如果链表是{2,2,1},而树里面存在一个path{2,2,2,1},结果应该返回true。但这个解法里面,读到第3个2的时候,发现不对,已经没法走回头路了。
应该在整个树里面,对每个节点都调用helper(),用前/中/后序遍历都可以。文章来源地址https://www.toymoban.com/news/detail-822298.html

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        origHead = head;
        origRoot = root;
        helper(head, root);
        return gPathExist;
    }
private:
    bool gPathExist = false;
    TreeNode *origRoot = NULL;
    ListNode *origHead = NULL;
    void helper(ListNode *head, TreeNode *root) {
        if (!head) {
            gPathExist = true;
            return;
        }
        if (!root || gPathExist) return;
        if (root->val == head->val) {
            helper(head->next, root->left);
            helper(head->next, root->right);
        } else {
            if (root == origRoot) {
                helper(origHead, root->left);
                helper(origHead, root->right);
            } else if (head != origHead) {
                helper(origHead, root);
                helper(origHead, root);
            }
        }
    }
};

到了这里,关于Leetcode 1367. Linked List in Binary Tree (二叉树好题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(41)
  • 数据结构第四天: Complete Binary Search Tree 【搜索二叉树,完全二叉树】

     这道题需要的操作时排序并且需要遍历,最重要的一点它是个完全二叉树,所以数组是最适合的 这道题我的思路来自于浙江大学课件7.0.2完全二叉树 这道题说白就是将输入的样例构造成一个完全搜索二叉树。因为完全线索二叉树的 根节点一定是是一个处于左右子树中间的那

    2024年02月06日
    浏览(55)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • LeetCode 1019. Next Greater Node In Linked List【单调栈模板】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2023年04月18日
    浏览(37)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(45)
  • 二叉搜索树(Binary_Search_Tree)

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。 它的左右子树也分别为二叉搜索树。 如: a、从根开始

    2024年04月28日
    浏览(40)
  • 【C++】二叉搜索树Binary Search Tree

    二叉搜索树又被称为二叉排序树,顾名思义,当我们使用中序遍历时,会得到一个有序的序列。二叉搜索树有如下的性质: 1.若它的左子树不为空,则左子树上每个节点的值都小于根节点的值。 2.若它的右子树不为空,则右子树上每个节点的值都大于根节点的值。 3.左右子树

    2024年02月07日
    浏览(49)
  • 二叉搜索树(Binary Search Tree,BST)

    二叉搜索树(Binary Search Tree),也称二叉查找树或二叉排序树,是一种特殊的二叉树,它满足以下性质 对于二叉搜索树的每个节点 左子树中的所有节点的值都小于该节点的值 右子树中的所有节点的值都大于(或等于)该节点的值 对于二叉搜索树的任意节点,其左子树和右子

    2024年02月09日
    浏览(46)
  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包