Java求解对称二叉树

标题：Java求解对称二叉树

public class TestSymmetricBinaryTree03 { /** * 使用递归测试对称二叉树 * 思想： * p * 1)p.left == p.right * 2)右子树 对称 左子树 * @param p * @return */ public boolean symmetricBinaryTree(TreeNode p) { if(p == null) { return true; } return symmetricBinaryTree02(p.left, p.right); } public boolean symmetricBinaryTree02(TreeNode p1, TreeNode p2) { if(p1 == null && p2 == null) { return true; }else if(p1 == null || p2 == null) { return false; }else {//都不为null if(p1.val != p2.val) { return false; } //相等 boolean res1 = symmetricBinaryTree02(p1.right, p2.left); boolean res2 = symmetricBinaryTree02(p1.left, p2.right); return res1 && res2; } } /** * 使用迭代求解 */ public boolean symmetricBinaryTree03(TreeNode p) { if(p == null) { return true; } if(p.left == null && p.right == null) { return true; }else if(p.left == null || p.right == null) { return true; } //都不为null Deque<TreeNode> s1 = new LinkedList<TreeNode>(); Deque<TreeNode> s2 = new LinkedList<TreeNode>(); s1.push(p.left); s2.push(p.right); while(!s2.isEmpty() && !s2.isEmpty()) { TreeNode node1 = s1.pop(); TreeNode node2 = s2.pop(); if(node1 == null && node2 == null) { continue; }else if(node1 == null || node2 == null) { return false; } //不为null if(node1.val != node2.val) { return false; } s1.push(node1.left); s1.push(node1.right); s2.push(node2.right); s2.push(node2.left); } if(s1.isEmpty() && s2.isEmpty()) { return true; } return false; } /** * 初始化一个tree * 类广度遍历 * @param a * @return */ public TreeNode initTree(Integer[] a) { if(a == null || a.length == 0) { return null; } int t = 0; TreeNode p = new TreeNode(a[t]); //至少有一个元素 Queue<TreeNode> q = new LinkedList<>(); q.offer(p); while(!q.isEmpty()) { TreeNode node = q.poll(); if(t + 1 == a.length) { //先判断数组中是否还有下一个元素 return p; }else { t++; if(a[t] == null) { //若下一个元素为null，则不需要创建新的节点 node.left = null; }else { node.left = new TreeNode(a[t]); q.offer(node.left); } } if(t + 1 == a.length) { return p; }else { t++; if(a[t] != null){ //上面的简写，a[t] == null，不需要再赋值 node.right = new TreeNode(a[t]); q.offer(node.right); } } } return p; } @Test public void test() { // Integer[] a = new Integer[] {1, 2, 2, 3, 4, 4, 3};//false // Integer[] a = new Integer[] {1, 2, 2, null, 3, null, 3};//false Integer[] a = new Integer[] {5, 3, 1, null, 1, null, 3, 2, null, 2, null};//false TreeNode p = this.initTree(a); System.out.println("使用递归"); System.out.println("istrue:" + this.symmetricBinaryTree(p)); System.out.println("使用迭代进行求解"); System.out.println("isTrue:" + this.symmetricBinaryTree03(p)); } }