Leetcode 1367:二叉树中的列表(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1367:二叉树中的列表(超详细的解法!!!)

in leetcode with 0 comment

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

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

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

示例 1:

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

示例 2:

输入: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
解释:二叉树中不存在一一对应链表的路径。

提示:

解题思路

树形问题首先思考递归解法,比较容易想到的思路就是以树中的每个节点作为head的起始点,然后向下遍历。那么我们需要两个函数来实现,通过$f_1$遍历所有树种的点,再通过$f_2$遍历每个点之后是否存在路径。

思考$f_1$的边界条件。如果head为空表示head表里结束了,返回True;如果root为空,显然表示后面没有路径了,而此时head不为空,那么返回False;如果head.val != root.val,那么返回False

$f_2$的边界条件在$f_1$中已经判断过了,只需要保证传入的参数合法即可。

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        def dfs1(h, node):
            if not h: return True
            if not node: return False
            if h.val != node.val: return False
            return dfs1(h.next, node.left) or dfs1(h.next, node.right)
        
        def dfs2(h, node):
            if dfs1(h, node): return True
            if not node: return False
            return dfs2(h, node.left) or dfs2(h, node.right)
        return dfs2(head, root)

能不能只通过一个函数实现呢?也可以,我们需要建立额外参数start记录是不是已经开始匹配了。边界条件和前面一样,当h.val != node.val的时候略有不同。如果此时start=True,表示已经开始匹配并且当前匹配失败,那么返回False;否则,返回$f(head,node.left)||f(head,node.right)$。

如果h.val = node.val,同样需要判断start。如果此时start=True,表示已经开始匹配并且当前匹配成功,那么返回$f(head.next,node.left)||f(head.next,node.right)$;否则,返回$f(head.next,node.left)||f(head.next,node.right)||f(head,node.left)||f(head,node.right)$。

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        
        def dfs(h, node, start):
            if not h: return True
            if not node: return False
            if h.val != node.val:
                if start: return False
                return dfs(h, node.left, False) or dfs(h, node.right, False)
            
            if start:
                return dfs(h.next, node.left, True) or dfs(h.next, node.right, True)
            return dfs(h.next, node.left, True) or dfs(h.next, node.right, True) or dfs(h, node.left, False) or dfs(h, node.right, False)
        return dfs(head, root, False)

但是显然这种做法是一种暴力解。实际上这个问题和字符串匹配非常类似,我们可以借鉴KMP算法的思想。

class Solution:
    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        arr, f = [], [-1]
        i, node = -1, head
        while node: # 计算next数组
            while i != -1 and node and node.val != arr[i]:
                i = f[i]
            i += 1
            f.append(i)
            arr.append(node.val)
            node = node.next

        def dfs(root, u):
            if not root: return False
            while u != -1 and root.val != arr[u]:
                u = f[u]
            u += 1
            if u == len(arr): return True
            return dfs(root.left, u) or dfs(root.right, u)
        return dfs(root, 0)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses