每天做一道算法題,循序漸進,按算法分類刷題。堅持下去,看能堅持多久,也看最終能有多大成效。
二叉樹中的列表
給你一棵以 root 為根的二叉樹和一個 head 為第一個節點的鏈表。
如果在二叉樹中,存在一條一直向下的路徑,且每個點的數值恰好一一對應以 head 為首的鏈表中每個節點的值,那麼請你返回 True ,否則返回 False 。
一直向下的路徑的意思是:從樹中某個節點開始,一直連續向下的路徑。
示例 1:
![每日算法練習20200409](http://p2.ttnews.xyz/loading.gif)
輸入: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](http://p2.ttnews.xyz/loading.gif)
輸入: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節點進行比較,如果全部比較通過,則說明存在這樣的子路徑。
實現代碼
參考銜接
https://leetcode-cn.com/problems/linked-list-in-binary-tree
閱讀更多 突破程序員 的文章