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));

	}

}