//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 com.llz.algorithm.algorithm2019.secondweek;

import com.llz.algorithm.algorithm2019.firstweek.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */

public class LeetCode_101_2 {

    /**
     * Time and space complexity is O(n), n is the number of nodes in the tree.
     * @param root
     * @return
     */
    public boolean isSymmetricByTraverse(TreeNode root) {
        return traverse(root, root);
    }

    public boolean traverse(TreeNode cur, TreeNode mirr) {
        if (cur == null && mirr == null)
            return true;
        if (cur == null || mirr == null) {
            return false;
        }
        if (cur.val != mirr.val)
            return false;
        return traverse(cur.left, mirr.right) && traverse(cur.right, mirr.left);

    }

    /**
     * Time and space complexity is O(n), n is the number of nodes in the tree.
     * However, traverse method is faster than the iteration method. I think it owns to
     * the cost of creation and the operation of the deque.
     * @param root
     * @return
     */
    public boolean isSymmetricByIteration(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        deque.add(root);
        TreeNode cur, mirr;
        while (!deque.isEmpty()) {
            cur = deque.poll();
            mirr = deque.poll();
            if (cur == null && mirr == null) continue;
            if (cur == null || mirr == null) return false;
            if (cur.val != mirr.val) return false;
            deque.add(cur.left);
            deque.add(mirr.right);
            deque.add(cur.right);
            deque.add(mirr.left);
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(5);
        LeetCode_101_2 s = new LeetCode_101_2();
        System.out.println(new LeetCode_101_2().isSymmetricByTraverse(root));
    }
}