首页 > 代码库 > [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 [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
思路：
递归法：当要比较的两个结点有一个为空时返回false，当要比较的两个结点值不相等时返回false。 当两结点为空时即为true。
非递归：层次遍历，需要注意的是左结点按照左右的顺序进入队列，而右边结点要按照先右后左顺序进入队列，这样比较的时候才满足是否对称要求。
bool isSymmetric2(TreeNode *root) {//非递归 层次遍历二叉树 TreeNode *left, *right; if (!root) return true; queue<TreeNode*> q1, q2; q1.push(root->left); q2.push(root->right); while (!q1.empty() && !q2.empty()){ left = q1.front(); q1.pop(); right = q2.front(); q2.pop(); if (NULL == left && NULL == right) continue; if (NULL == left || NULL == right) return false; if (left->val != right->val) return false; q1.push(left->left); q1.push(left->right); q2.push(right->right); q2.push(right->left); } return true; } bool isSymmetricCore(TreeNode* left, TreeNode* right) { if (left == NULL && right == NULL) return true; if (left == NULL && right != NULL || left != NULL && right == NULL || left->val != right->val)return false; return isSymmetricCore(left->left, right->right) && isSymmetricCore(left->right, right->left);//递归判断 } bool isSymmetric(TreeNode* root) { if (root == NULL) return true; return isSymmetricCore(root->left, root->right); }
参考：
https://discuss.leetcode.com/topic/4332/my-c-accepted-code-in-16ms-with-iteration-solution
[leetcode-101-Symmetric Tree]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。