package question;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
    @author: Roderland
    @create: 2020-08-14---15:09
*/
public class Question101 {
    public static void main(String[] args) {
        //[1,2,2,3,4,4,3]
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(2);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(4);
        TreeNode t6 = new TreeNode(4);
        TreeNode t7 = new TreeNode(3);
        t1.left=t2;
        t1.right=t3;
        t2.left=t4;
        t2.right=t5;
        t3.left=t5;
        t3.right=t7;
        System.out.println(new Question101().isSymmetric(t1));
    }
    List<TreeNode> list1 = new ArrayList<>();
    List<TreeNode> list2 = new ArrayList<>();
    public boolean isSymmetric(TreeNode root) {
        if (root==null) return true;
        lastOrderTraverse1(root.left);
        lastOrderTraverse2(root.right);
        if (list1.size()!=list2.size()) return false;
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i)==null&&list2.get(i)==null) continue;
            else if (list1.get(i)==null||list2.get(i)==null) return false;
            else if (list1.get(i).val!=list2.get(i).val) return false;
        }
        return true;
    }
    public void lastOrderTraverse1(TreeNode root) {
        if (root==null) {
            list1.add(null);
            return;
        }
        lastOrderTraverse1(root.left);
        lastOrderTraverse1(root.right);
        list1.add(root);
    }
    public void lastOrderTraverse2(TreeNode root) {
        if (root==null) {
            list2.add(null);
            return;
        }
        lastOrderTraverse2(root.right);
        lastOrderTraverse2(root.left);
        list2.add(root);
    }
    //solution2
    public boolean isSymmetric2(TreeNode root) {
        if (root==null) return true;
        return fun(root.left, root.right);
    }
    public boolean fun(TreeNode left, TreeNode right) {
        if (left==null||right==null) return left==right;
        return left.val==right.val&&fun(left.left, right.right)&&fun(left.right, right.left);
    }
    //solution3
    public boolean isSymmetric3(TreeNode root) {
        if (root==null) return true;
        Stack<TreeNode> leftStack = new Stack<>();
        Stack<TreeNode> rightStack = new Stack<>();
        leftStack.push(root.left);
        rightStack.push(root.right);
        while (!leftStack.isEmpty()&&!rightStack.isEmpty()) {
            TreeNode left = leftStack.pop();
            TreeNode right = rightStack.pop();
            if (left==null&&right==null) continue;
            else if (left==null||right==null) return false;
            else if (left.val!=right.val) return false;
            leftStack.push(left.left);
            leftStack.push(left.right);
            rightStack.push(right.right);
            rightStack.push(right.left);
        }
        return true;
    }
}