468 · Symmetric Binary Tree - LintCode

Description

Given a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example

Example 1:

Input: {1,2,2,3,4,4,3}
Output: true
Explanation:
         1
        / \
       2   2
      / \ / \
      3 4 4 3

is a symmetric binary tree.

Example 2:

Input: {1,2,2,#,3,#,3}
Output: false
Explanation:
         1
        / \
        2  2
        \   \
         3   3

is not a symmetric binary tree.

Challenge

Can you solve it both recursively and iteratively?

# Solution

要滿足鏡像的條件：

# DFS

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/

	public class Solution {
	/**
	* @param root: the root of binary tree.
	* @return: true if it is a mirror of itself, or false.
	*/
	public boolean isSymmetric(TreeNode root) {
	if(root == null){
	return true;
	}
	return check(root.left, root.right);


	}
	private boolean check (TreeNode root1, TreeNode root2){
	if(root1 == null & root2 == null) {
	return true;
	}
	if(root1 == null \|\| root2 == null) {
	return false;
	}
	if(root1.val != root2.val){
	return false;
	}
	return check(root1.left, root2.right) && check(root1.right, root2.left);
	}
	}

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/

	public class Solution {
	/**
	* @param root: the root of binary tree.
	* @return: true if it is a mirror of itself, or false.
	*/
	public boolean isSymmetric(TreeNode root) {
	return check(root, root);
	}

	public boolean check(TreeNode root1, TreeNode root2) {
	Queue<TreeNode> queue = new LinkedList<>();
	queue.offer(root1);
	queue.offer(root2);

	while (!queue.isEmpty()) {
	root1 = queue.poll();
	root2 = queue.poll();
	if (root1 == null && root2 == null) continue;
	if (root1 == null \|\| root2 == null) return false;
	if (root1.val != root2.val) return false;

	queue.offer(root1.left);
	queue.offer(root2.right);

	queue.offer(root1.right);
	queue.offer(root2.left);
	}
	return true;
	}
	}