1.题目描述

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

For example, this binary tree is symmetric:

1

/ \

2   2

/ \ / \

3  4 4  3

But the following is not:

1

/ \

2   2

\   \

3    3

Note:

Bonus points if you could solve it both recursively and iteratively.

2.解法分析

这个题目其实可以看做是深度搜索的变种，深度搜索有三种：先序、中序和后序，对于这个题目，我们对root的左右子树同时进行先序深度搜索，所不同的是，左子树的深度搜索是“左右”顺序，右子树是“右左”顺序，只要直到深度搜索完成都满足同步，那么这棵树满足要求。

/**

* Definition for binary tree

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

bool isSymmetric(TreeNode *root) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(!root)return true;

vector
           
            left_traversal;
           

vector
           
            right_traversal;
           

TreeNode * cur_left = root->left;

TreeNode *cur_right = root->right;

if((cur_left!=NULL&&cur_right==NULL)||(cur_left==NULL&&cur_right!=NULL))return false;

if(cur_left==NULL&&cur_right==NULL)return true;

while(!left_traversal.empty()||cur_left)

{

while(cur_left)

{

if(!cur_right)return false;

if(cur_left->val!=cur_right->val)return false;

left_traversal.push_back(cur_left);

right_traversal.push_back(cur_right);

cur_left= cur_left->left;

cur_right = cur_right->right;

}

if(!left_traversal.empty())

{

if(cur_right)return false;

cur_left=left_traversal.back();left_traversal.pop_back();

cur_right=right_traversal.back();right_traversal.pop_back();

cur_left = cur_left->right;

cur_right = cur_right->left;

}

}l

if(!left_traversal.empty()||!right_traversal.empty())return false;

if(cur_left&&cur_right)return cur_left->val==cur_right->val;

else

{

if(!cur_left&&!cur_right)return true;

else return false;

}

return true;

}

};