作者：青雲算法
來源：https://blog.csdn.net/QingyunAlgo/article/details/86302835
分析：
這是LeetCode的第951題。
按照題目中翻轉等價的定義，如果兩棵二叉樹翻轉等價，那麼首先它們的根節點要相同。如果根節點不同，那麼兩棵二叉樹一定不是翻轉等價。
接下來看左右子樹是否翻轉等價。這裡要分兩種情況討論。第一種可能是不用交換根節點的左右子樹，此時分別判斷第一棵樹的左子樹和第二棵樹的左子樹是否翻轉等價，以及第一棵樹的右子樹和第二棵樹的右子樹是否翻轉等價。第二種可能是需要交換根節點的左右子樹，此時分別判斷第一棵樹的左子樹和第二棵樹的右子樹是否翻轉等價，以及第一棵樹的右子樹和第二棵樹的左子樹是否翻轉等價。
怎麼判斷子樹翻轉等價？這和判斷整棵樹翻轉等價是同一個問題，可以遞歸解決。參考代碼如下：
由於需要遍歷整棵樹，因此時間複雜度是O(n)，n為二叉樹中節點的數目。
分享到:
閱讀更多 程序員聖經 的文章
