Title:
Symmetric Binary - Strategy 1
Link to LeetCode:
https://leetcode.com/problems/symmetric-tree/
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;
}
}