101. Symmetric Tree
Easy
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1 / 2 2 / / 3 4 4 3
But the following [1,2,2,null,3,null,3]
is not:
1 / 2 2 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
package leetcode.easy; /** * Definition for a binary tree node. public class TreeNode { int val; TreeNode * left; TreeNode right; TreeNode(int x) { val = x; } } */ public class SymmetricTree { public boolean isSymmetric1(TreeNode root) { return isMirror(root, root); } public boolean isMirror(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) { return true; } if (t1 == null || t2 == null) { return false; } return (t1.val == t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right); } public boolean isSymmetric2(TreeNode root) { java.util.Queue<TreeNode> q = new java.util.LinkedList<>(); q.add(root); q.add(root); while (!q.isEmpty()) { TreeNode t1 = q.poll(); TreeNode t2 = q.poll(); if (t1 == null && t2 == null) { continue; } if (t1 == null || t2 == null) { return false; } if (t1.val != t2.val) { return false; } q.add(t1.left); q.add(t2.right); q.add(t1.right); q.add(t2.left); } return true; } @org.junit.Test public void test1() { TreeNode tn11 = new TreeNode(1); TreeNode tn21 = new TreeNode(2); TreeNode tn22 = new TreeNode(2); TreeNode tn31 = new TreeNode(3); TreeNode tn32 = new TreeNode(4); TreeNode tn33 = new TreeNode(4); TreeNode tn34 = new TreeNode(3); tn11.left = tn21; tn11.right = tn22; tn21.left = tn31; tn21.right = tn32; tn22.left = tn33; tn22.right = tn34; tn31.left = null; tn31.right = null; tn32.left = null; tn32.right = null; tn33.left = null; tn33.right = null; tn34.left = null; tn34.right = null; System.out.println(isSymmetric1(tn11)); System.out.println(isSymmetric2(tn11)); } @org.junit.Test public void test2() { TreeNode tn11 = new TreeNode(1); TreeNode tn21 = new TreeNode(2); TreeNode tn22 = new TreeNode(2); TreeNode tn32 = new TreeNode(4); TreeNode tn34 = new TreeNode(3); tn11.left = tn21; tn11.right = tn22; tn21.left = null; tn21.right = tn32; tn22.left = null; tn22.right = tn34; tn32.left = null; tn32.right = null; tn34.left = null; tn34.right = null; System.out.println(isSymmetric1(tn11)); System.out.println(isSymmetric2(tn11)); } }