【二叉樹】二叉樹中的清單

0x00 題目

給你一棵以 ​

​root ​

​​為根的二叉樹

和一個 ​​

​head​

​ 為第一個節點的連結清單

如果在二叉樹中，存在一條一直​

​向下​

​​的路徑

且​​

​每個點​

​​的數值恰好一一對應以 ​

​head​

​​ 為首的

連結清單中每個節點的值，那麼請你傳回 ​​

​True​

​​ ，否則傳回 ​

​False​

​

一直向下的路徑的意思是：

從樹中某個節點開始，一直連續向下的路徑

0x01 思路

枚舉二叉樹中的​

​每個​

​​節點

為​​

​起點​

​​往下的路徑

是否有與連結清單相​​

​比對​

​的路徑

0x02 解法

語言：​

​Swift​

​

樹節點：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func isSubPath(_ head: ListNode?, _ root: TreeNode?) -> Bool {
    func dfs(_ head: ListNode?, _ root: TreeNode?) -> Bool {
        // 連結清單已經全部比對完
        if head == nil { return true }
        
        // 二叉樹通路到了空節點
        if root == nil { return false }
        
        // 值不相等
        if head!.val != root!.val { return false }
        
        // 值相等，繼續遞歸比對
        return dfs(head!.next, root!.left) || dfs(head!.next, root!.right)
    }
    
    guard let root = root else { return false }
    // 判斷根節點
    let b1 = dfs(head, root)
    
    // 判斷子節點
    let b2 = isSubPath(head, root.left)
    let b3 = isSubPath(head, root.right)
    
    return b1 || b2 || b3
}      

0x03 我的小作品