[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);
}
Show Comments