Symmetric Tree[LeetCode]对称二叉树

https://leetcode.com/problems/symmetric-tree/

题目：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.

confused what"{1,#,2,3}"means?> read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1 / \ 2 3/ 4\5The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

非递归解决方法（层次遍历算法）：

#include<iostream>#include<queue>#include<vector>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};//层序遍历方法解决class Solution {public:bool isSymmetric(TreeNode *root) {queue<TreeNode *> iqueue; vector<TreeNode *> ivec; //回文判断是否对称TreeNode teminateNode(INT_MAX); //使用INT_MAX代替#if(root!=NULL)iqueue.push(root);elsereturn true; //空树是对称的，直接返回truewhile(!iqueue.empty()){ //层序遍历结束条件，其实是用不到的,可以改成while(true)while(!iqueue.empty()){ //遍历队列，，直到为空TreeNode *temp=iqueue.front();iqueue.pop();if(temp->val!=INT_MAX){if(temp->left!=NULL)ivec.push_back(temp->left);else ivec.push_back(&teminateNode);if(temp->right!=NULL)ivec.push_back(temp->right);else ivec.push_back(&teminateNode);}}if(ivec.empty()) //如果树对称，则ivec肯定为空return true;//如果ivec不为空时，判断是否对称，实质判断是否为回文vector<TreeNode*>::iterator biter=ivec.begin();vector<TreeNode*>::iterator eiter=ivec.end()-1;while(biter<eiter){if((*biter)->val!=(*eiter)->val)return false;//不对称，返回falsebiter++;eiter–;}//把ivec内容顺序压入队列，然后清空ivecfor(int i=0;i<ivec.size();i++)iqueue.push(ivec[i]);ivec.clear();}}};递归解决方法：class Solution {public:bool isSymmetric(TreeNode *root) {if(root==NULL) //空树返回truereturn true;elsereturn isSymmetric(root->left,root->right);}bool isSymmetric(TreeNode* lroot,TreeNode* rroot){if(lroot==NULL && rroot==NULL) //全为空return true;if(lroot==NULL || rroot==NULL)//有一个为空，肯定不对称return false;if(lroot->val!=rroot->val)//值不相等肯定不对称return false;bool isLeft=isSymmetric(lroot->left,rroot->right);//判断左左和右右是否相等bool isRight=isSymmetric(lroot->right,rroot->left);//判断左右和右左是否相等return isLeft&&isRight; //都相等时，才为true}};

就是去旅行。牵着彼此的手，

相关文章：

你感兴趣的文章：

标签云：