leetcode 101. 对称二叉树 Symmetric Tree(使用c++/java/python)
https://leetcode-cn.com/problems/symmetric-tree/
https://leetcode.com/problems/symmetric-tree/
递归。利用一个函数判断两颗树是否镜像对称,即需要满足:
- 两树根节点相同
- 树1的左子树与树2的右子树镜像
- 树1的右子树与树2的左子树镜像
执行用时: c++ 8ms; java 15ms; python 48ms
c++
/**
* Definition for a binary tree node.
* 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;
else
return ismirror(root->left, root->right);
}
bool ismirror(TreeNode* n1,TreeNode* n2)
{
if (n1==NULL && n2==NULL)
return true;
if (n1==NULL || n2==NULL)
return false;
return (n1->val==n2->val)&&(ismirror(n1->left,n2->right))&&(ismirror(n1->right,n2->left));
}
};
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)
return true;
else
return ismirror(root.left,root.right);
}
public boolean ismirror(TreeNode root1,TreeNode root2)
{
if(root1==null && root2==null)
return true;
if(root1==null || root2==null)
return false;
return root1.val==root2.val && ismirror(root1.left,root2.right) && ismirror(root1.right,root2.left);
}
}
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
else:
return self.ismirror(root.left,root.right)
def ismirror(self,root1,root2):
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
return root1.val==root2.val and self.ismirror(root1.left,root2.right) and self.ismirror(root1.right,root2.left)