首页 > 代码库 > LeetCode: Symmetric Tree 解题报告
LeetCode: Symmetric Tree 解题报告
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.
SOL 1 & 2:
两个解法，递归和非递归.
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 // solution 1:12 public boolean isSymmetric(TreeNode root) {13 if (root == null) {14 return true;15 }16 17 return isSymmetricTree(root.left, root.right);18 }19 20 /*21 * 判断两个树是否互相镜像 22 (1) 根必须同时为空，或是同时不为空23 * 24 * 如果根不为空: 25 (1).根的值一样 26 (2).r1的左树是r2的右树的镜像 27 (3).r1的右树是r2的左树的镜像28 */29 public boolean isSymmetricTree1(TreeNode root1, TreeNode root2) {30 if (root1 == null && root2 == null) {31 return true;32 }33 34 if (root1 == null || root2 == null) {35 return false;36 }37 38 return root1.val == root2.val && 39 isSymmetricTree(root1.left, root2.right) && 40 isSymmetricTree(root1.right, root2.left);41 }42 43 // solution 2:44 public boolean isSymmetricTree(TreeNode root1, TreeNode root2) {45 if (root1 == null && root2 == null) {46 return true;47 }48 49 if (root1 == null || root2 == null) {50 return false;51 }52 53 Stack<TreeNode> s1 = new Stack<TreeNode>();54 Stack<TreeNode> s2 = new Stack<TreeNode>();55 56 // 一定记得初始化57 s1.push(root1);58 s2.push(root2);59 60 while (!s1.isEmpty() && !s2.isEmpty()) {61 TreeNode cur1 = s1.pop();62 TreeNode cur2 = s2.pop();63 64 if (cur1.val != cur2.val) {65 return false;66 }67 68 if (cur1.left != null && cur2.right != null) {69 s1.push(cur1.left);70 s2.push(cur2.right);71 } else if (!(cur1.left == null && cur2.right == null)) {72 return false;73 }74 75 if (cur1.right != null && cur2.left != null) {76 s1.push(cur1.right);77 s2.push(cur2.left);78 } else if (!(cur1.right == null && cur2.left == null)) {79 return false;80 }81 }82 83 return true;84 }85 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/IsSymmetric.java
LeetCode: Symmetric Tree 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。