題目

https://leetcode.com/problems/symmetric-tree/

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.

解答

C#

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSymmetric(TreeNode root)
    {
        if (root == null)
            return true;
        else
            return IsSymmetricTree(root.left, root.right);
    }

    public bool IsSymmetricTree(TreeNode left, TreeNode right)
    {
        if (left == null || right == null)
            return left == right;
        if (left.val != right.val)
            return false;
        return IsSymmetricTree(left.left, right.right) && IsSymmetricTree(left.right, right.left);
    }
}

結果

Runtime: 88 ms, faster than 99.39% of C# online submissions.

Memory Usage: 23.8 MB, less than 27.27% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

LinkedList 結束之後，我們要開始來解另一個常見的資料結構 Tree

什麼是 Tree 呢？根據 wiki 的定義

n（n>0）個有限節點組成一個具有層次關係的集合。

特徵如下：

1. 每個節點都只有 有限 個子節點或無子節點
2. 沒有父節點的節點稱為 根節點
3. 每一個非根節點只有 一個 父節點
4. 除了根節點外，每個子節點可以分為多個 不相交 的子樹
5. 樹裡面 沒有 cycle

有了以上的基本認識，我們再來講講為什麼要這樣寫
其實這題最簡單的解法是 遞迴 Recursion，而且淺顯易懂

1. 在原本的 method 裡判斷根節點是否為 null
   • 若 是 則回傳 true
   • 若 否 則透過另一個 method IsSymmetricTree 將左右節點做判斷
     • 若左節點或右節點為 null，則回傳他們是否一樣 left == right
     • 判斷左節點的值是否等於右節點的值
       • 若 否 則回傳 false
       • 若 是 則再繼續判斷左節點的子節點、右節點的子節點
         • left.left, right.right
         • left.right, right.left

只要有一個 false，回傳的結果都會為 false。

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

以 [1, 2, 2, 3, 4, 4, 3] 為例，程式就會照下列的順序去巡覽。

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉