package code;
/*
 * 101. Symmetric Tree
 * 
 * Easy
 * Tree, DFS, BFS
 * Tips
 *  left.leftright.right, left.rightright.left 
 */
import java.util.Stack;

public class lc101 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public boolean isSymmetric(TreeNode root) {
        //
        if(root==null)
            return true;

        Stack s = new Stack();
        s.push(root.left);
        s.push(root.right);
        while(!s.isEmpty()){
            TreeNode tn1 = s.pop(), tn2 = s.pop();
            if(tn1==null||tn2==null)
                if(tn1 == tn2)  //
                    continue;
                else
                    return false;
            if(tn1.val!=tn2.val)
                return false;
            s.push(tn1.left);
            s.push(tn2.right);
            s.push(tn1.right);
            s.push(tn2.left);
        }
        return true;
    }

    // 
    public boolean isSymmetric2(TreeNode root) {
        return root==null || func(root.left, root.right);
    }

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