Title:

Symmetric Binary - Strategy 1

Specification:

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

Examples:

Example 1:

This binary tree [1,2,2,3,4,4,3] is symmetric.

Example 2:

But the following [1,2,2,null,3,null,3] is not.

Initial Code and Signature:

``` public class SymmetryCheckerV2 { public boolean isSymmetric(TreeNode root) { } } ```

Algorithm:

1- Start from root
2- Read the nodes in each level
3- Is the level Palindrome?
4- No: Return false
4- Yes: Go to the next level
5- Return true

Run-Time Analysis:

GitHub Project:

Code:

``` import java.util.*; /** * * @author Mahsa Sadi * @since 2020-02-10 * * * Problem: Given a binary tree, check whether it is a mirror of itself * (i.e.; it is symmetric around its center.) * * Solution2: * 1- Start from root * 2- Read Nodes in each level * 3- Is the level Palindrome? * 4- No: Return False; * 4- Yes: Go to the next level * * @see LeetCode Problem: Symmetric Binary Tree -> https://leetcode.com/problems/symmetric-tree/submissions/ * */ public class SymmetryCheckerV2 implements SymmetryChecker { public boolean isSymmetric(TreeNode root) { List currentLevel = new ArrayList(); List nextLevel = new ArrayList(); /** * 1- Start from root. */ currentLevel.add(root); while (!currentLevel.isEmpty()) { /** * 2- Read each Level. 3- IsPalindrome? */ if (!isPalindrome(currentLevel)) return false; /** * 4- Go to the next level. */ else { for (int i = 0; i < currentLevel.size(); i++) { if ( currentLevel.get(i) != null) { TreeNode lc = currentLevel.get(i).getLeftChild(); nextLevel.add(lc); TreeNode rc = currentLevel.get(i).getRightChild(); nextLevel.add(rc); } } currentLevel = nextLevel; nextLevel = new ArrayList(); } } return true; } public boolean isPalindrome(List currentLevel) { for (int i = 0; i < currentLevel.size() / 2; i++) { try { if (currentLevel.get(i).getValue() != currentLevel.get(currentLevel.size() - 1 - i).getValue()) { return false; } } catch (Exception NullPointerException) { if (currentLevel.get(i) == null && currentLevel.get(currentLevel.size() - 1 - i) != null) return false; else { if (currentLevel.get(i) != null && currentLevel.get(currentLevel.size() - 1 - i) == null) return false; } } } return true; } } ```