# LeetCode Easy 101. Symmetric Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

与えられた木が左右対称な木か判断する問題です．

これは与えられた木の部分木も左右対称となるので，その結果を用いて解くことにします．

解法1(recursive)

下の図のようになっているかを再帰的に関数を使って確かめます．

• 根が空ならtrue
• 空でないなら左右のノードを使って以下のように確かめます
  • 左右共にない(nullptr)ならtrue
  • 左右のどちらかしかないならfalse
  • 左右の値が同じ
    • 左の左==右の右
    • 左の右==右の左

計算量

ノードの数は$N$とします

• 時間計算量
  • (大体)各々のノードで関数を実行するので$O(N)$
• 空間計算量
  • 再帰の深さが$O(\log N)$なので$O(\log N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    if (!root)
      return true;
    return isMirror(root->left, root->right);
  }
private:
  bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right)
      return true;
    if (!left || !right)
      return false;
    return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);
  }
};

解法2(iterative)

BFSのときはQueue, DFSのときはStackが有効です

今回は前者で探索しているのでQueueを選択して解きます．

計算量

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    if (!root)
      return true;
    queue<TreeNode*> q_left, q_right;
    q_left.push(root->left);
    q_right.push(root->right);
    
    while (!q_left.empty() && !q_right.empty()) {
      auto left = q_left.front();
      auto right = q_right.front();
      q_left.pop(), q_right.pop();
      
      if (!left && !right)
        continue;
      if (!left || !right)
        return false;
      if (left->val != right->val)
        return false;
      
      q_left.push(left->left);
      q_left.push(left->right);
      q_right.push(right->right);
      q_right.push(right->left);
    }
    return true;
  }
};