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