Symmetric Tree 镜像树

问题

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

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

思路

先写出大框架，需要分别判断左右节点，所以额外定义一个传入左右节点的函数。同时向根节点的左边两边遍历比较。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
        {
            return false;
        }
        return isSymmetric(root->left, root->right);
    }

    bool isSymmetric(TreeNode* left, TreeNode* right) {
        return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
    }
};

判断是否平衡，采用前序遍历。若当前节点镜像，不返回值，继续向下遍历判断。直到节点为空，不断向上返回true。
完成代码如下

class Solution {
public:

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

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

非递归解法，二刷再来。