请实现一个函数,用来判断一棵二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
思路: 新建一个镜像二叉树,然后再来比较两个二叉树是否相同。 难点,另外构建2个辅助函数,2个辅助函数中分别递归。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
// 辅助函数用于翻转二叉树(镜像二叉树)
TreeNode invertTree(TreeNode root) {
if(root == null) {return null;}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
boolean judgeSame(TreeNode p, TreeNode n) {
if (p == null && n == null) {
return true;
}
if (p == null || n == null) {
return false;
}
return p.val == n.val && judgeSame(p.left, n.right) && judgeSame(p.right, n.left);
}
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) return true;
TreeNode nRoot = pRoot;
//引入辅助函数invertTree,通过翻转二叉树,生成一个镜像二叉树
invertTree(nRoot);
// 引入辅助函数judgeSame,来判断二叉树 和 镜像二叉树是否相同
return judgeSame(pRoot, nRoot);
}
}
如下解法,进行了一定的优化。 因为根节点不需要再进行比较,直接 递归比较根节点的左右子树即可。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean judgeSame(TreeNode p, TreeNode n) {
if(p == null && n == null) {return true;}
if(p == null || n == null) {return false;}
return p.val == n.val && judgeSame(p.left, n.left) && judgeSame(p.right, n.right);
}
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) return true;
// 引入辅助函数judgeSame,来判断二叉树 和 镜像二叉树是否相同
return judgeSame(pRoot.left, pRoot.right);
}
}