题解 | JZ28 对称的二叉树
C++和python分别用了两种写法做的本题。
C++采用的思路是创建一颗和它左右子树交换的树，然后再判断这颗左右子树交换的树和它原本的树结构是不是相同。如果相同，那么这颗树就是对称的树。
python采用的思路是直接对这棵树进行判断，利用isSame(p1, p2)函数来对当前的节点进行判断，如果相同，需要满足：
- p1.val == p2.val
- p1.left.val == p2.right.val
- p1.right.val == p2.left.val
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot) {
TreeNode* Root = makeTree(pRoot);
return isSame(Root, pRoot);
}
TreeNode* makeTree(TreeNode* Root) {
if (!Root) return nullptr;
TreeNode* tmp = new TreeNode(Root->val);
tmp->right = makeTree(Root->left);
tmp->left = makeTree(Root->right);
return tmp;
}
bool isSame(TreeNode* p1, TreeNode* p2) {
if ((p1&&!p2) || (!p1&&p2)) return false;
if (!p1&&!p2) return true;
if (p1->val != p2->val) return false;
return isSame(p1->left, p2->left) && isSame(p1->right, p2->right);
}
};
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
return self.isSame(pRoot, pRoot)
def isSame(self, p1, p2):
if not p1 and not p2:
return True
if not p1 or not p2:
return False
return p1.val == p2.val and self.isSame(p1.left, p2.right) and self.isSame(p1.right, p2.left)
查看16道真题和解析
