首页 > 代码库 > 对称树 Symmetric Tree
对称树 Symmetric Tree
算法能力一直不好，决定利用晚上和假期时间多做点算法题，动动手，提高自己。大家看到我的水平低还望莫要嘲笑，嘻嘻。
这一题呢是LeetCode上的对称树问题，
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / 2 2 / \ / 3 4 4 3
But the following is not:
1 / 2 2 \ 3 3
一开始没能够全面的思考树的情况，单纯理解为对称树即对称的完全二叉树，于是首先想到的就是直接对树进行层次遍历，对每一层进行对称性检验。结果提交时发现，其实如下图这种树也是对称的
1 / 2 2 / 3 3
后来思考能否通过树的中序遍历来判断是否对称，但结果也是不可以的。如下图这棵树：
1 / 2 3 / / 3 2
只能换一种思路啦，对于对称树某一层上的两个相对称节点来说，节点A的左子树与B的右子树对称，节点A的右子树与B的左子树对称。所以可以直接使用递归算法，初始为(root,root)对，然后根据前面的规律递归。
public static boolean isSymmetric(TreeNode root) { return isSys(root,root);} public static boolean isSys(TreeNode l,TreeNode r){ if(l==null && r==null) return true; if(l==null || r==null) return false; if(l.val!=r.val) return false; boolean left = isSys(l.left , r.right); boolean right = isSys(l.right,r.left); return left&&right;}
若不用递归的方法，则可以设置两个队列，push左右子树的节点进行比较。（一个队列先左后右，另一个先右后左）
public static boolean isSymmetric1(TreeNode root){ if(root==null)return true; Queue<TreeNode> lt = new LinkedList<TreeNode>(); Queue<TreeNode> rt = new LinkedList<TreeNode>(); if(root.left!=null) lt.add(root.left); if(root.right!=null) rt.add(root.right); TreeNode l; TreeNode r; while(!lt.isEmpty() && !rt.isEmpty()) { l = lt.poll(); r = rt.poll(); if(l == null && r == null) continue; if(l == null || r == null) return false; if(l.val != r.val) return false; lt.add(l.left); lt.add(l.right); rt.add(r.right); rt.add(r.left); } if(lt.isEmpty() && rt.isEmpty()) return true; else return false; }
对称树 Symmetric Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。