Question

Formatted question description: https://leetcode.ca/all/101.html

101	Symmetric Tree

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

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:
    1
   / \
  2   2
   \   \
   3    3
Note:
Bonus points if you could solve it both recursively and iteratively.

@tag-tree

Algorithm

It is necessary to compare whether the value of the left child node of n1 and the value of the right child node of n2 are equal, and also whether the value of the right child node of n1 and the value of the left child node of n2 are equal.

Code

Java

import java.util.Stack;

public class Symmetric_Tree {

	public static void main(String[] args) {

	}

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

	public class Solution_iteration {
	    public boolean isSymmetric(TreeNode root) {

	        if (root == null) {
	        	return true;
	        }


	        Stack<TreeNode> sk1 = new Stack<TreeNode>();
	        Stack<TreeNode> sk2 = new Stack<TreeNode>();

	        sk1.push(root.left);
	        sk2.push(root.right);

	        while (!sk1.isEmpty() && !sk2.isEmpty()) {
		        TreeNode r1 = sk1.pop();
		        TreeNode r2 = sk2.pop();

		        if (r1 == null && r2 == null) {
		        	continue;
		        } else if (r1 == null && r2 != null) {
		        	return false;
		        } else if (r1 != null && r2 == null) {
		        	return false;
		        } else if (r1.val != r2.val) {
		        	return false;
		        }

		        sk1.push(r1.left);
		        sk2.push(r2.right);

		        sk1.push(r1.right);
		        sk2.push(r2.left);
	        }

	        // @note: not necessary, since sk1 and sk2 are the same size, push/pop side by side
	        // if (!sk1.isEmpty() || !sk2.isEmpty()) {
	        // 	return false;
	        // }

	        return true;
	    }
	}

	public class Solution_recursion {
	    public boolean isSymmetric(TreeNode root) {

	        if (root == null) {
	        	return true;
	        }

	        return check(root.left, root.right);
	    }

	    private boolean check(TreeNode r1, TreeNode r2) {
	        if (r1 == null && r2 == null) {
	        	return true;
	        } else if (r1 == null && r2 != null) {
	        	return false;
	        } else if (r1 != null && r2 == null) {
	        	return false;
	        } else {
	        	return r1.val == r2.val
	        			&& check(r1.left, r2.right) && check(r1.right, r2.left);
	        }

	    }
	}

}

All Problems

All Solutions