21.对称二叉树-LeetCode-Java

给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 进阶： 你可以运用递归(深度周游)和迭代(广度周游)两种方法解决这个问题吗？ /** * 方法一：先序遍历=后序遍历的逆序 * 对称二叉树 左 = 右 * 先序遍历：根左右 * 后序遍历：左右根 = 右左根(左=右) 所以先序遍历=后序遍历的逆序 */ class Solution { Queue queue = new LinkedList(); Stack stack = new Stack(); public boolean isSymmetric(TreeNode root) { preOrder(root); postOrder(root); while (!queue.isEmpty() && !stack.isEmpty()) { if (!queue.poll().equals(stack.pop())) return false; } return true; } public void preOrder(TreeNode root) { if (root != null) { queue.add(root.val); preOrder(root.left); preOrder(root.right); } else queue.add("N"); } public void postOrder(TreeNode root) { if (root != null) { postOrder(root.left); postOrder(root.right); stack.push(root.val); } else stack.push("N"); } } /** * 方法二：递归(分治思想) * 镜像对称：左边根值 = 右边根值 && isMirror(左边的左边,右边的右边) && isMirror(左边的右边,右边的左边) */ class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isMirror(root.left, root.right); } private boolean isMirror(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left); } } /** * 方法三：层次遍历(广度周游) * 镜像对称：左右必定是成双成对,层次遍历二叉树时将"成对"的元素放入队列,每次出队列两个元素,比较是否是一对。 */ class Solution { Queue queue = new LinkedList(); public boolean isSymmetric(TreeNode root) { if (root == null || (root.left == null && root.right == null)) return true; // 0层或者1层 if (root.left != null && root.right != null) return levelOrder(root.left, root.right); // 2+层 return false; } /** * 第二层开始 * 左边的左边和右边的右边是一对 左边的右边和右边的左边是一对 */ private boolean levelOrder(TreeNode rootLeft, TreeNode rootRight) { queue.add(rootLeft); queue.add(rootRight); while (!queue.isEmpty()) { // 左边的左边和右边的右边 左边的右边和右边的左边一起入队列 TreeNode t1 = (TreeNode) queue.poll(); TreeNode t2 = (TreeNode) queue.poll(); if (t1 != null && t2 != null) { if (t1.val != t2.val) return false; queue.add(t1.left); queue.add(t2.right); queue.add(t1.right); queue.add(t2.left); } else if (t1 == null && t2 == null) { } else { return false; } } return true; } }