首页 > 代码库 > 【LeetCode题目记录-11】判断二叉树是否是镜像的(对称的)
【LeetCode题目记录-11】判断二叉树是否是镜像的(对称的)
Symmetric Tree
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
Note:
Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
【分析1-原创】采用递归方案,查看了参考才搞定。
参考:https://oj.leetcode.com/discuss/456/recusive-solution-symmetric-optimal-solution-inordertraversal
public static boolean isSymmetric(TreeNode root) { if(root==null) return true; return checkIsSymmetric(root.left,root.right); } private static boolean checkIsSymmetric(TreeNode leftNode,TreeNode rightNode) { if(leftNode==null&&rightNode==null) return true; if((leftNode!=null&&rightNode==null)||(leftNode==null&&rightNode!=null)) return false; if(leftNode.val!=rightNode.val) return false; return checkIsSymmetric(leftNode.left,rightNode.right)&&checkIsSymmetric(leftNode.right,rightNode.left); }
【分析2-非原创】用stack对左右进行进stack,然后每一层进行比较。
参考:https://oj.leetcode.com/discuss/456/recusive-solution-symmetric-optimal-solution-inordertraversal
public boolean isSymmetric(TreeNode root) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (root == null) return true; Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); s1.push(root.left); s2.push(root.right); while (!s1.empty() && !s2.empty()) { TreeNode n1 = s1.pop(); TreeNode n2 = s2.pop(); if (n1 == null && n2 == null) continue; if (n1 == null || n2 == null) return false; if (n1.val != n2.val) return false; s1.push(n1.left); s2.push(n2.right); s1.push(n1.right); s2.push(n2.left); } return true; }
【LeetCode题目记录-11】判断二叉树是否是镜像的(对称的)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。