首页 > 代码库 > [Leetcode] Symmetric Tree
[Leetcode] 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.
Solution 1: recursive
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 public boolean isSymmetric(TreeNode root) {12 if (root == null)13 return true;14 return mySymmetric(root.left,root.right);15 16 }17 18 private boolean mySymmetric(TreeNode left, TreeNode right) {19 // TODO Auto-generated method stub20 if(left==null&&right==null)21 return true;22 if(left==null||right==null)23 return false;24 return (left.val==right.val)&&mySymmetric(left.right, right.left)&&mySymmetric(left.left, right.right);25 }26 }
Solution 2: iterative
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 public boolean isSymmetric(TreeNode root) {12 //iterative way13 if(root==null)14 return true;15 Stack<TreeNode> sl=new Stack<TreeNode>();16 Stack<TreeNode> sr=new Stack<TreeNode>();17 sl.add(root.left);18 sr.add(root.right);19 while(!sl.isEmpty()&&!sr.isEmpty()){20 TreeNode n1=sl.pop();21 TreeNode n2=sr.pop();22 if(n1==null&&n2==null)23 continue;24 if(n1==null||n2==null)25 return false;26 if(n1.val!=n2.val)27 return false;28 sl.push(n1.left);29 sl.push(n1.right);30 sr.push(n2.right);31 sr.push(n2.left);32 }33 return true;34 }35 }
[Leetcode] Symmetric Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。