leetcode--Symmetric Tree

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<TreeNode *>left_traversal;
        vector<TreeNode *>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;
    }

};