【LeetCode】101. 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==0) return true;
        return isSameTree(root->left, root->right);
    }
    
    bool isSameTree(TreeNode* left, TreeNode* right) {
    	if(left==0&&right==0) return true;
    	if(left!=0&&right==0||left==0&&right!=0||left->val!=right->val) return false;
    	return isSameTree(left->left, right->right)&&isSameTree(left->right, right->left);
    }
};