Title:
Symmetric Binary Tree - Strategy 2
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 SymmetryCheckerV3 {
public boolean isSymmetric(TreeNode root) {
}
}
Algorithm:
Recursive Version:
Run-Time Analysis:
GitHub Project:
Code:
import java.util.*;
/**
*
* @author Mahsa Sadi
* @since 2020-02-13
*
*/
public class SymmetryCheckerV3 implements SymmetryChecker {
/**
* Symmetry Checker Version 3:
*
* Recursive Algorithm:
*
* 1- Divide the tree into Left-Tree and Right-Tree
* 2- Left Traverse Left Tree recursively
* 3- Right Traverse Right Tree recursively
* 4- Check whether the sequence obtained from both traversals are equal.
*
*
* leftTraverse / rightTraverse:
*
* 1-meet left child / meet right child
* 2-meet right child / meet left child
* 3-mild root / meet root
*
* or
*
* 1-meet left child / meet right child
* 2-meet root / meet root
* 3-meet right child / meet left child
*/
List lTResult;
List rTResult;
public boolean isSymmetric(TreeNode root) {
lTResult = new ArrayList();
rTResult = new ArrayList();
TreeNode lr, rr;
if ( root == null)
return true;
else {
lr = root.getLeftChild();
rr = root.getRightChild();
if (lr == null) {
if (rr == null)
return true;
else
return false;
}
else if (rr == null) {
if (lr == null)
return true;
else
return false;
}
else if (lr.getValue() != rr.getValue())
return false;
else {
leftTraverse(lr);
rightTraverse(rr);
return isEqual(lTResult, rTResult);
}
}
}
public boolean isEqual(List l1, List l2) {
if (l1.size() != l2.size())
return false;
else {
for (int i = 0; i < l1.size(); i++)
if (l1.get(i) != l2.get(i))
return false;
}
return true;
}
public void leftTraverse(TreeNode root) {
if (root == null)
lTResult.add(null);
else if (isLeaf(root))
lTResult.add(root.getValue());
else {
TreeNode lc = root.getLeftChild();
if (lc != null)
leftTraverse(lc);
else
lTResult.add(null);
TreeNode rc = root.getRightChild();
if (rc != null)
leftTraverse(rc);
else
lTResult.add(null);
lTResult.add(root.getValue());
}
}
public void rightTraverse(TreeNode root) {
if (root == null)
rTResult.add(null);
else if (isLeaf(root))
rTResult.add(root.getValue());
else {
TreeNode rc = root.getRightChild();
if (rc != null)
rightTraverse(rc);
else
rTResult.add(null);
TreeNode lc = root.getLeftChild();
if (lc != null)
rightTraverse(lc);
else
rTResult.add(null);
rTResult.add(root.getValue());
}
}
public boolean isLeaf(TreeNode n) {
return n.getLeftChild() == null && n.getRightChild() == null;
}
}