[LeetCode Road] Symmetric Tree - Solution/C++

101. Symmetric Tree

Question:

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

Example:

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

Source code:

Version 1

Idea:
The strategic is similar to Same-Tree. First, we must check the root node whether it's null or not. Then, we use root->left and root->right as arguments to call private function.

There are some rules we must to know:
1. the value of the left node must be equal to the value of the right node.
2. the value of the left node as the left child node must be equal to the value of the right node as the right child node.
3. the vlaue of the left node as the right child node must be equal to the value of the right node as the left child node.
So, we can write to codes based on these ruls at 22~23 line.

Time complexity: O(n)
Space complexity: O(n)

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