package week02;

import java.util.LinkedList;

import java.util.Queue;

/**

* @创建人 luoxiang

* @创建时间 2019/6/14 15:06

* @描述 LeetCode : 101. 对称二叉树 https://leetcode-cn.com/problems/symmetric-tree/

*/

public class SymmetricTree101 {

public static void main(String[] args) {

TreeNode node = new TreeNode(3);

node.left = new TreeNode(2);

node.right = new TreeNode(2);

node.left.left = new TreeNode(3);

node.left.right = new TreeNode(4);

node.right.left = new TreeNode(4);

node.right.right = new TreeNode(3);

System.out.println(new SymmetricTree101().isSymmetric(node));

}

/**

* Method 1 : BFS ，使用队列

* 添加顺序：

* 1、左子树的左

* 2、右子树的右

* 3、左子树的右

* 4、右子树的左

* 时间复杂度 : O(N) ;

* 空间复杂度 : O(N) ;

*/

public boolean isSymmetric(TreeNode root) {

if (root == null || (root.left==null && root.right==null)) return true;

Queue<TreeNode> queue = new LinkedList<>();

queue.offer(root.left);

queue.offer(root.right);

while (!queue.isEmpty()) {

TreeNode node = queue.poll();

TreeNode node2 = queue.poll();

if (node == null && node2 == null) continue;

if (node == null || node2 == null) return false;

if (node.val != node2.val) return false;

queue.offer(node.left);

queue.offer(node2.right);

queue.offer(node.right);

queue.offer(node2.left);

}

return true;

}

/**

* Method 2 : DFS

* 时间复杂度 ： O(N)

* 空间复杂度 ： O(N)

*/

public boolean isSymmetric2(TreeNode root) {

return isMirrer(root, root);

}

private boolean isMirrer(TreeNode root, TreeNode root1) {

if (root == null && root1 == null) return true;

if (root == null || root1 == null) return false;

if (root.val != root1.val) return false;

return isMirrer(root.left, root1.right) && isMirrer(root.right, root1.left);

}

/**

* Method 2 : DFS 优化版

* 时间复杂度 ： O(N)

* 空间复杂度 ： O(N)

*/

public boolean isSymmetric3(TreeNode root) {

if (root == null) return true;

return isMirrer3(root.left, root.right);

}

private boolean isMirrer3(TreeNode left, TreeNode right) {

if (left == null && right == null) return true;

if (left == null || right == null) return false;

return (left.val == right.val) && isMirrer3(left.left, right.right) && isMirrer3(left.right, right.left);

}

}