本文共 1109 字,大约阅读时间需要 3 分钟。
题目描述
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
分析
考虑将二叉树复制一份,如果二叉树是对称的,那么对于同一位置上的节点(记为root1和root2),必须同时满足这些条件:
牛客AC:
/*public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { /** * 请实现一个函数,用来判断一颗二叉树是不是对称的。 * 注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 * @param pRoot * @return */ boolean isSymmetrical(TreeNode pRoot) { return isSymmetrical(pRoot, pRoot); } boolean isSymmetrical(TreeNode pRoot1, TreeNode pRoot2) { if(pRoot1 == null && pRoot2 == null) // 同时为空,true return true; if(pRoot1 == null || pRoot2 == null) // 只有一个为空,false return false; if(pRoot1.val != pRoot2.val) // 节点的值不相等,false return false; // 左节点等于右节点,右节点等于左节点 return isSymmetrical(pRoot1.left, pRoot2.right) && isSymmetrical(pRoot1.right, pRoot2.left); }}
参考
1. 何海涛,剑指offer名企面试官精讲典型编程题(纪念版),电子工业出版社转载地址:http://pkxgi.baihongyu.com/