请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
方法一:递归调用
1 /* 2 public class TreeNode { 3 int val = 0; 4 TreeNode left = null; 5 TreeNode right = null; 6 public TreeNode(int val) { 7 this.val = val; 8 } 9 } 10 */ 11 public class Solution { 12 boolean isSymmetrical(TreeNode pRoot){ 13 if(pRoot==null) 14 return true; //根结点为null时，认为是对称二叉树 15 return isEqual(pRoot.left,pRoot.right); 16 } 17 private boolean isEqual(TreeNode pRoot1,TreeNode pRoot2){ 18 //左右结点都为空 19 if(pRoot1==null && pRoot2==null) 20 return true; 21 //一个结点有值,另一个结点为null,肯定不对称 22 if(pRoot1==null || pRoot2==null) 23 return false; 24 //递归调用 25 return pRoot1.val==pRoot2.val 26 && isEqual(pRoot1.left, pRoot2.right) 27 && isEqual(pRoot1.right, pRoot2.left); 28 } 29 }
方法二:队列或堆栈
我认为,很多树的问题都可以用这两个结构来解决,这是方向性的问题
使用stack来保存成对的节点
2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
1 import java.util.Stack; 2 public class Solution { 3 boolean isSymmetrical(TreeNode pRoot){ 4 //考虑特殊情况,空树为对称的树 5 if(pRoot == null) return true; 6 //入栈 7 Stack<TreeNode> s = new Stack<>(); 8 s.push(pRoot.left); 9 s.push(pRoot.right); 10 while(!s.empty()) { 11 //成对出栈,上面是左结点,右结点,所以出栈是右结点,左结点 12 TreeNode right = s.pop(); 13 TreeNode left = s.pop(); 14 if(left == null && right == null) continue;//跳出本次while循环,继续下一次while循环 15 if(left == null || right == null) return false; 16 if(left.val != right.val) return false; 17 //成对插入 18 s.push(left.left); 19 s.push(right.right); 20 s.push(left.right); 21 s.push(right.left); 22 } 23 return true; 24 } 25 }
队列的思想,和堆栈的类似,只不过是先进先出而已
1 import java.util.Queue; 2 import java.util.LinkedList; 3 public class Solution { 4 boolean isSymmetrical(TreeNode pRoot){ 5 if(pRoot == null) return true; 6 Queue<TreeNode> s = new LinkedList<>(); 7 s.offer(pRoot.left); 8 s.offer(pRoot.right); 9 while(!s.isEmpty()) { 10 //成对取出 11 TreeNode left = s.poll(); 12 TreeNode right = s.poll(); 13 if(left == null && right == null) continue; 14 if(left == null || right == null) return false; 15 if(left.val != right.val) return false; 16 //成对插入 17 s.offer(left.left); 18 s.offer(right.right); 19 s.offer(left.right); 20 s.offer(right.left); 21 } 22 return true; 23 } 24 }
原文：https://www.cnblogs.com/shareidea94/p/11168378.html