Symmetric Binary Tree (Ladder)

Description

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

Example

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

is a symmetric binary tree.

    1
   / \
  2   2
   \   \
   3    3

is not a symmetric binary tree.

Challenge:
Can you solve it both recursively and iteratively?

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition of TreeNode:
   * class TreeNode {
   * public:
   *     int val;
   *     TreeNode *left, *right;
   *     TreeNode(int val) {
   *         this->val = val;
   *         this->left = this->right = NULL;
   *     }
   * }
   */
   class Solution {
   public:
    /**
     * @param root, the root of binary tree.
     * @return true if it is a mirror of itself, or false.
     */
    bool isSymmetric(TreeNode* root) {
        // Write your code here
        if (!root) {
            return true;
        }
        return helper(root->left, root->right);
    }
    bool helper(TreeNode* left, TreeNode* right) {
        if (!left && !right) {
            return true;
        }
        if (!left || !right) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        return helper(left->left, right->right) && helper(left->right, right->left);
    }
   };
   

Similar problems

x

Tags

x