101. 對稱二叉樹
難度簡單930 收藏 分享 切換為英文 關(guān)注 反饋
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1
/
2 2
/ \ /
3 4 4 3
</pre>
但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1
/
2 2
\
3 3
</pre>
進階：
你可以運用遞歸和迭代兩種方法解決這個問題嗎？
遞歸解法
C++：
class Solution {
public:
bool checkSym(TreeNode* lroot,TreeNode* rroot){
if (lroot==NULL && rroot==NULL) return true;
if (lroot==NULL || rroot==NULL) return false;
if (lroot->val != rroot->val) return false;
return checkSym(lroot->left,rroot->right)&&checkSym(lroot->right,rroot->left);
}
bool isSymmetric(TreeNode* root) {
if (root==NULL) return true;
return checkSym(root->left,root->right);
}
};
優(yōu)化答案：
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
對應(yīng)python寫法：
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def check(l:TreeNode, r: TreeNode) -> bool:
if (not l and not r):
return True
if (not l or not r):
return False
return l.val == r.val and check(l.left, r.right) and check(l.right, r.left)
return check(root,root)
