每日算法練習20200409

每天做一道算法題,循序漸進,按算法分類刷題。堅持下去,看能堅持多久,也看最終能有多大成效。

二叉樹中的列表

給你一棵以 root 為根的二叉樹和一個 head 為第一個節點的鏈表。

如果在二叉樹中,存在一條一直向下的路徑,且每個點的數值恰好一一對應以 head 為首的鏈表中每個節點的值,那麼請你返回 True ,否則返回 False 。

一直向下的路徑的意思是:從樹中某個節點開始,一直連續向下的路徑。

示例 1:

每日算法練習20200409

輸入:head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]

輸出:true

解釋:樹中藍色的節點構成了與鏈表對應的子路徑。

示例 2:

每日算法練習20200409

輸入: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 之間。

解決方案

先序遍歷樹的每一個節點,對於每個節點如果和head的值相等,則遞歸該節點的左子樹和右子樹 與 head的next節點進行比較,如果全部比較通過,則說明存在這樣的子路徑。

實現代碼


每日算法練習20200409

參考銜接

https://leetcode-cn.com/problems/linked-list-in-binary-tree


分享到:


相關文章: