题目:
请实现一个函数, 用来判断一颗二叉树是不是对称的. 注意, 如果一个二叉树同此二叉树的镜像是同样的, 定义其为对称的.
分析:
从根结点开始递归对比左右子树即可. 需要注意的是, 当前左右两个结点相同比较下面的结点时, 由于是判断二叉树是否是对称的, 递归执行时, 比较的两个结点是当前左结点的左结点和当前右结点的右结点去比较, 这样才是对称的.
程序:
- C++
- class Solution {
- public:
- bool isSymmetrical(TreeNode* pRoot)
- {
- if(pRoot == nullptr)
- return true;
- return isSame(pRoot->left, pRoot->right);
- }
- bool isSame(TreeNode* p1, TreeNode* p2){
- if(p1 == nullptr && p2 == nullptr)
- return true;
- if(p1 == nullptr || p2 == nullptr)
- return false;
- if(p1->val != p2->val)
- return false;
- return isSame(p1->left, p2->right) && isSame(p1->right, p2->left);
- }
- };
- Java
- public class Solution {
- boolean isSymmetrical(TreeNode pRoot)
- {
- if(pRoot == null)
- return true;
- return isSame(pRoot.left, pRoot.right);
- }
- boolean isSame(TreeNode p1, TreeNode p2){
- if(p1 == null && p2 == null)
- return true;
- if(p1 == null || p2 == null)
- return false;
- if(p1.val != p2.val)
- return false;
- return isSame(p1.left, p2.right) && isSame(p1.right, p2.left);
- }
- }
来源: http://www.bubuko.com/infodetail-3355885.html