【题目】
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;
}//if
return 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;
}//if
return 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;
}//if
stack<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);
}//while
return true;
}
};
【复杂度二】
时间复杂度 O(n),空间复杂度 O(logn)
分享到:
相关推荐
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
lru缓存leetcode ...https://leetcode.com/problems/symmetric-tree/ Symmetric Tree 102 https://leetcode.com/problems/binary-tree-level-order-traversal/ Binary Tree Level Order Traversal 103 ...
101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-...
leetcode 答案 LeetCode-Trip ...Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]
leetcode 树节点leetcode 测试 仅使用适用于python 方便本地测试,ListNode和TreeNode类型 # filename leetcode.py from leetcode_test ...isSymmetric(self, ...symmetric(left, ...tree = TreeNode.create
isSymmetric(TreeNode root) { if(root == NULL) return true; return checkSymmetric(root->left, root->right); } bool checkSymmetric(TreeNode* left, TreeNode* right) { if(left == NULL && right == NULL) ...
Symmetric tree - Java Recursive - Java Iterative - C Recursive - Python Iterative 0102 Binary Tree Level Order Traversal - Python3 iterative 0103 Binary Tree Zigzag Level Order Traversal - ...
leetcode分发糖果 Leetcode C++ Solution Don't try to understand it, feel ...21-合并两个有序链表:merge-two-sorted-lists 83-删除排序链表中的重复元素:remove-duplicates-from-sorted-...101-对称二叉树:symmetric-
tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param { TreeNode } root * @return { boolean } */ var isSymmetric = function ( root ) { if ( root ...
Symmetric Tree Balanced Binary Tree Flatten Binary Tree to Linked List Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct ...
对称的二叉树(递归,清晰图解)# Definition for a binary tree node.def isSymmetric(self, root: T