每天做一道算法題,循序漸進,按算法分類刷題。堅持下去,看能堅持多久,也看最終能有多大成效
翻轉等價二叉樹
我們可以為二叉樹 T 定義一個翻轉操作,如下所示:選擇任意節點,然後交換它的左子樹和右子樹。
只要經過一定次數的翻轉操作後,能使 X 等於 Y,我們就稱二叉樹 X 翻轉等價於二叉樹 Y。
編寫一個判斷兩個二叉樹是否是翻轉等價的函數。這些樹由根節點 root1 和 root2 給出。
示例:
輸入:root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
輸出:true
解釋:我們翻轉值為 1,3 以及 5 的三個節點。
![每日算法練習20200424](http://p2.ttnews.xyz/loading.gif)
提示:
每棵樹最多有 100 個節點。
每棵樹中的每個值都是唯一的、在 [0, 99] 範圍內的整數。
解決方案
這道題是對稱二叉樹的加強版,常規的判斷相等的基礎上,每個節點加一個翻轉相等的判斷。
實現代碼
![每日算法練習20200424](http://p2.ttnews.xyz/loading.gif)
參考鏈接
https://leetcode-cn.com/problems/flip-equivalent-binary-trees
https://leetcode-cn.com/problems/flip-equivalent-binary-trees/solution/fan-zhuan-deng-jie-er-cha-shu-by-leetcode/
閱讀更多 突破程序員 的文章