[LeetCode 解題筆記] Symmetric Tree

原問題網址：101. Symmetric Tree

問題描述

給定一棵 Binary Tree 的 root ，檢查其結構是否圍繞中心對稱（左右子樹就像鏡子反射一樣）。

解題思路

1. 使用遞迴解決。
2. 如果它沒有左子樹也沒有右子樹，必為 true 。
3. 如果有左子樹但沒有右子樹，或是有右子樹但沒有左子樹，必為 false ，因為左右一定不對稱。
4. 定義另一個 function is_mirror 檢查兩棵 Binary Tree 是否互為鏡像。

• 兩棵 Binary Tree 的 root 的 value 一定要相等，否則必為 false 。
• 比較 tricky 的部分：如果第一棵 tree 的左子點為 NULL ，第二棵 tree 的右子點也一定要為 NULL ，否則為 false ，反之亦然。

以下為用 C 語言實作的程式碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool is_mirror(struct TreeNode* root1, struct TreeNode* root2) {
  if (root1 == NULL || root2 == NULL) {
    return false;
  }
  if (root1->val != root2->val) {
    return false;
  }
  if (root1->left == NULL && root2->right != NULL) {
    return false;
  }
  if (root1->right == NULL && root2->left != NULL) {
    return false;
  }
  if (root1->left != NULL) {
    if (!is_mirror(root1->left, root2->right)) {
      return false;
    }
  }
  if (root1->right != NULL) {
    if (!is_mirror(root1->right, root2->left)) {
      return false;
    }
  }
  return true;
}

bool isSymmetric(struct TreeNode* root){
  if (root->left == NULL && root->right == NULL) {
    return true;
  }
  if (root->left == NULL || root->right == NULL) {
    return false;
  }
    
  return is_mirror(root->left, root->right);
}