[LeetCode]101.Symmetric Tree

本文主要是介绍[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 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.

【分析】

无

【代码】

/*********************************
*   日期：2014-12-24
*   作者：SJF0115
*   题目: 101.Symmetric Tree
*   来源：https://oj.leetcode.com/problems/symmetric-tree/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
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) {if(root == NULL){return true;}//ifreturn isSymmetric(root->left,root->right);}
private:bool isSymmetric(TreeNode *l,TreeNode *r) {// 两个节点都为空if(l == NULL && r == NULL){return true;}//if// 两个节点一个为空一个不为空if(l == NULL || r == NULL){return false;}//if// 两个节点val相同// 判断l的左子结点和r的右子节点// 判断l的右子结点和r的左子节点if(l->val == r->val){bool leftVal = isSymmetric(l->left,r->right);bool rightVal = isSymmetric(l->right,r->left);return leftVal && rightVal;}//ifreturn false;}
};//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){int data;//按先序次序输入二叉树中结点的值,-1表示空树cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//构造左子树CreateBTree(T->left);//构造右子树CreateBTree(T->right);}return 0;
}int main() {Solution solution;TreeNode* root(0);CreateBTree(root);cout<<solution.isSymmetric(root);
}

【复杂度】

时间复杂度 O(n)，空间复杂度 O(logn)

【代码二】

class Solution {
public:bool isSymmetric(TreeNode* root) {if(root == NULL){return true;}//ifstack<TreeNode*> stack;stack.push(root->left);stack.push(root->right);TreeNode *p,*q;// 迭代while(!stack.empty()){// 出栈p = stack.top();stack.pop();q = stack.top();stack.pop();// 两个节点都为空if(p == NULL && q == NULL){continue;}//if// 两个节点一个为空一个不为空if(p == NULL || q == NULL){return false;}//if// 两个节点val不相同if(p->val != q->val){return false;}//if// 判断p的左子结点和q的右子节点入栈stack.push(p->left);stack.push(q->right);// 判断p的右子结点和q的左子节点入栈stack.push(p->right);stack.push(q->left);}//whilereturn true;}
};