/**
1. mirror -> 
    1.1 子树左节点值 == 子树的右节点值 
    1.2 子树右节点.右儿子 same mirror 子树左节点.左儿子
    1.3 子树右节点.左儿子 same mirror 子树左节点.右儿子
2. edge case:
    1. root == null is mirror
    2. childs both are null is mirror
    3. only one child is null not mirror

*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isSymmetric(root.left, root.right);
    }

    boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null || right == null) return left == right;

        return left.val == right.val && isSymmetric(left.right, right.left) && isSymmetric(left.left, right.right);
    }
}

version at: 2020-02-04

/*
1. mirro的中序遍历一定对称，但中序遍历对称不一定是mirror [1,2,2,2,null,2]

2. 递归解法: 
2.1 dfs 顺序：判断当前位置对称的两个node是否val相等
2.2 dfs 状态：相互比较的两个对称点->  左左vs右右 && 左右vs右左
2.3 剪枝： null

3. 迭代解法：用栈模拟，左边按『左中右』顺序，右边按『右中左』顺序遍历比较
*/


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // return root == null || isMirror(root);
        // return root == null || recursively(root.left, root.right);
        return root == null || iteratively(root.left, root.right);
    }

    public void inorder(TreeNode root, List<Integer> list){
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    public boolean isMirror(TreeNode root){
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        int l = 0, r = list.size()-1;
        while (l < r){
            if (list.get(l) != list.get(r)) return false;
            l ++;
            r --;
        }
        return list.size() % 2 == 1;
    }

    public boolean recursively(TreeNode left, TreeNode right){
        if (left == null || right == null) return left == right;
        return left.val == right.val && recursively(left.left, right.right) && recursively(left.right, right.left);
    }

    public boolean iteratively(TreeNode left, TreeNode right){
        if (left == null || right == null) return left == right;
        Stack<TreeNode> stackLeft = new Stack<>();
        Stack<TreeNode> stackRight = new Stack<>();

        var pl = left;
        var pr = right;

        //while((pl!= null && pr != null) || (!stackLeft.empty() && !stackRight.empty())){
        while(pl!= null || pr != null || !stackLeft.empty() || !stackRight.empty()){
            while(true){
                if (pl != pr && (pl == null || pr == null ))  return false;
                if (pl == null && pr == null ) break;
                stackLeft.add(pl);
                pl = pl.left;
                stackRight.add(pr);
                pr = pr.right;
            }

            pl = stackLeft.pop();
            pr = stackRight.pop();

            if (pl.val != pr.val) return false;
            pl = pl.right;
            pr = pr.left;   

        }

        return true;
    }
}