[LeetCode] 101. Symmetric Tree

轉自LeetCode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

<Solution>

這題是要看一個 binary tree 是否有對稱性

題目有說使用 recursive 和 iterative 兩種解法來解

先來看 recursive 的解法

想法和 Same Tree 中的 recursive 解法一樣

變化的地方在於，不是檢查兩個樹的左子樹和右子樹是否一樣

而是檢查 node1 的左子樹和 node2 的右子樹，以及 node1 的右子樹和 node2 的左子樹是否一樣

code 如下
c++

kotlin
再來看 iterative 的解法

想法一樣，檢查node1 的左子樹和 node2 的右子樹，以及 node1 的右子樹和 node2 的左子樹是否一樣

只是這次準備一個 queue 去存 node (不一定要用 queue，用 list 或是 stack 都可以)

每次就丟對稱的 node 進去 queue，然後檢查時，一次拿兩個 node 出來檢查

code 如下
c++