Каков алгоритм основы для тестирования, если дерево симметрично. Поскольку это двоичное дерево, я бы предположил, что это будет рекурсивное определение видов
Формальный вопрос ниже:
Двоичное дерево является зеркальным отображением самого себя, если его левое и правое поддеревья являются идентичными зеркальными изображениями, т.е. бинарное дерево является симметричным. Это лучше всего объяснить несколькими примерами.
1
/ \
2 2
ИСТИНА
1
/ \
2 2
\
3
FALSE
1
/ \
2 2
/ \ / \
4 3 3 4
ИСТИНА
1
/ \
2 2
/ \ / \
3 4 3 4
FALSE
1
/ \
2 2
/ \
3 3
ИСТИНА
На выбранном языке программирования определите структуру BTree class/C и связанный с ней метод, чтобы проверить, является ли дерево зеркальным отображением. Для статически типизированных языков вы можете предположить, что значения node являются целыми числами.
Class/structure definition
BTree {
BTree left;
BTree right;
int value;
}
Предположим, что корень дерева отслеживается вызывающим и функция isMirror() вызывается на нем.
Кроме того, если вы определяете класс, не забудьте предоставить конструкторы без аргументов и методы getter/setter, если элементы данных недоступны.
Как насчет вызова mirrorEquals (root.left, root.right) для следующей функции: -
boolean mirrorEquals(BTree left, BTree right) {
if (left == null || right == null) return left == null && right == null;
return left.value == right.value
&& mirrorEquals(left.left, right.right)
&& mirrorEquals(left.right, right.left);
}
В основном сравнить левое поддерево и инвертированное правое поддерево, вырисовывая воображаемую линию инверсии через корень.
Решение 1 - Рекурсивно:
bool isMirror(BinaryTreeNode *a, BinaryTreeNode *b)
{
return (a && b) ?
(a->m_nValue==b->m_nValue
&& isMirror(a->m_pLeft,b->m_pRight)
&& isMirror(a->m_pRight,b->m_pLeft)) :
(a == b);
}
bool isMirrorItselfRecursively(BinaryTreeNode *root)
{
if (!root)
return true;
return isMirror(root->m_pLeft, root->m_pRight);
}
Решение 2 - Итеративно:
bool isMirrorItselfIteratively(BinaryTreeNode *root)
{
/// use single queue
if(!root) return true;
queue<BinaryTreeNode *> q;
q.push(root->m_pLeft);
q.push(root->m_pRight);
BinaryTreeNode *l, *r;
while(!q.empty()) {
l = q.front();
q.pop();
r = q.front();
q.pop();
if(l==NULL && r==NULL) continue;
if(l==NULL || r==NULL || l->m_nValue!=r->m_nValue) return false;
q.push(l->m_pLeft);
q.push(r->m_pRight);
q.push(l->m_pRight);
q.push(r->m_pLeft);
}
return true;
}
Рекурсивное решение из @gvijay очень ясно, и здесь итерационное решение.
Осмотрите каждую строку дерева сверху вниз и посмотрите, являются ли значения палиндром. Если все они тогда, да, это зеркало. Вам нужно будет реализовать алгоритм, чтобы посещать каждую строку и включать в себя нулевые значения для редких деревьев. В псевдокоде:
boolean isMirror(BTree tree) {
foreach (List<Integer> row : tree.rows() {
if (row != row.reverse()) return false;
}
return true;
}
Хитрость заключается в том, чтобы разработать алгоритм для итерации строк дерева с учетом того, что разреженные деревья должны иметь нулевые значения в качестве владельцев мест. Эта реализация Java выглядит нормально:
public static boolean isMirror(BTree root) {
List<BTree> thisRow, nextRow;
thisRow = Arrays.asList(root);
while (true) {
// Return false if this row is not a palindrome.
for (int i=0; i<thisRow.size()/2; i++) {
BTree x = thisRow.get(i);
BTree y = thisRow.get(thisRow.size()-i-1);
if ((x!=null) && (y!=null)
&& (x.value != y.value))
return false;
if (((x==null) && (y!=null))
|| (x!=null) && (y==null))
return false;
}
// Move on to the next row.
nextRow = new ArrayList<BTree>();
for (BTree tree : thisRow) {
nextRow.add((tree==null) ? null : tree.lt);
nextRow.add((tree==null) ? null : tree.rt);
}
boolean allNull = true;
for (BTree tree : nextRow) {
if (tree != null) allNull = false;
}
// If the row is all empty then we're done.
if (allNull) return true;
thisRow = nextRow;
}
}
Рекурсивные и итеративные решения в Java с использованием рассмотренных выше подходов
Рекурсивный
public Boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetricInternal(root.left, root.right);
}
private Boolean isSymmetricInternal(TreeNode leftNode,
TreeNode rightNode) {
boolean result = false;
// If both null then true
if (leftNode == null && rightNode == null) {
result = true;
}
if (leftNode != null && rightNode != null) {
result = (leftNode.data == rightNode.data)
&& isSymmetricInternal(leftNode.left, rightNode.right)
&& isSymmetricInternal(leftNode.right, rightNode.left);
}
return result;
}
Итеративный, используя LinkedList в качестве очереди
private Boolean isSymmetricRecursive(TreeNode root) {
boolean result = false;
if (root == null) {
return= true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
result = true;
}
else if (left == null ||
right == null ||
left.data != right.data) {
// It is required to set result = false here
result = false;
break;
}
else if (left != null && right != null) {
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
}
return result;
}
Контрольный пример
@Test
public void testTree() {
TreeNode root0 = new TreeNode(1);
assertTrue(isSymmetric(root0));
assertTrue(isSymmetricRecursive(root0));
TreeNode root1 = new TreeNode(1, new TreeNode(2), new TreeNode(2));
assertTrue(isSymmetric(root1));
assertTrue(isSymmetricRecursive(root1));
TreeNode root2 = new TreeNode(1,
new TreeNode(2, null, new TreeNode(3)), new TreeNode(2));
assertFalse(isSymmetric(root2));
assertFalse(isSymmetricRecursive(root2));
TreeNode root3 = new TreeNode(1, new TreeNode(2, new TreeNode(4),
new TreeNode(3)), new TreeNode(2, new TreeNode(3),
new TreeNode(4)));
assertTrue(isTreeSymmetric(root3));
assertTrue(isSymmetricRecursive(root3));
TreeNode root4 = new TreeNode(1, new TreeNode(2, new TreeNode(3),
new TreeNode(4)), new TreeNode(2, new TreeNode(3),
new TreeNode(4)));
assertFalse(isSymmetric(root4));
assertFalse(isSymmetricRecursive(root4));
}
Дерево Node класс
public class TreeNode {
int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data){
this(data, null, null);
}
public TreeNode(int data, TreeNode left, TreeNode right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
ИЗМЕНИТЬ
Как было отмечено в комментариях, моя первая версия алгоритма не удалась для определенных входов. Я не собираюсь изобретать колесо, я просто предоставляю ответ на Python, используя правильный алгоритм @gvijay. Во-первых, представление для двоичного дерева:
class BTree(object):
def __init__(self, l, r, v):
self.left = l
self.right = r
self.value = v
def is_mirror(self):
return self._mirror_equals(self.left, self.right)
def _mirror_equals(self, left, right):
if left is None or right is None:
return left is None and right is None
return (left.value == right.value
and self._mirror_equals(left.left, right.right)
and self._mirror_equals(left.right, right.left))
Я тестировал приведенный выше код, используя все образцы деревьев в вопросе и деревья, которые возвращали неверные результаты, как указано в комментариях. Теперь результаты верны для всех случаев:
root1 = BTree(
BTree(None, None, 2),
BTree(None, None, 2),
1)
root1.is_mirror() # True
root2 = BTree(
BTree(None, BTree(None, None, 3), 2),
BTree(None, None, 2),
1)
root2.is_mirror() # False
root3 = BTree(
BTree(
BTree(None, None, 4),
BTree(None, None, 3),
2),
BTree(
BTree(None, None, 3),
BTree(None, None, 4),
2),
1)
root3.is_mirror() # True
root4 = BTree(
BTree(
BTree(None, None, 3),
BTree(None, None, 4),
2),
BTree(
BTree(None, None, 3),
BTree(None, None, 4),
2),
1)
root4.is_mirror() # False
root5 = BTree(
BTree(BTree(None, None, 3), None, 2),
BTree(None, BTree(None, None, 3), 2),
1)
root5.is_mirror() # True
root6 = BTree(BTree(None, None, 1), None, 1)
root6.is_mirror() # False
root7 = BTree(BTree(BTree(None, None, 1), None, 2), None, 1)
root7.is_mirror() # False
Вот решение С++ на gvijay
bool isMirrorTree(BTnode* LP, BTnode* RP)
{
if (LP == NULL || RP == NULL) // if either is null check that both are NULL
{
return ( LP == NULL && RP == NULL );
}
// check that data is equal and then recurse
return LP->data == RP->data &&
isMirrorTree( LP->left, RP->right ) &&
isMirrorTree( LP->right, RP->left );
}
Ниже приведено решение относительно C-COde
isMirror(root)
{
Symmetric(root->left, root->right);
}
Symmetric(root1,root2)
{
if( (root1->left EX-NOR root2->right) && (root1->right EX-NOR root2->left) && (root1->value==root2->value) )
//exnor operation will return true if either both present or both not present
// a EX-NOR b =(!a && !b) || (a && b))
{
Symmetric(root1->left, root2->right);
Symmetric(root1->right, root2->left);
}
else return false;
}
Немного другой подход.
Как проделать обход внутри двоичного дерева, хранящего все содержимое в некоторой структуре данных, например строку/массив.
Как только обход завершен, проверьте, являются ли элементы в вашем массиве палиндром. Не так эффективно пространство (рекурсия принимает O (log (n)), этот метод показывает O (n)), но это также будет работать.
Итеративное решение с использованием немного другого подхода в python. Используйте queue1 для хранения левых детей в порядке слева направо и queue2 для хранения прав детей в порядке справа налево и сравнения для равенства.
def isSymmetric(root):
if not root:
return True
if not (root.left or root.right):
return True
q1 = collections.deque([root.left])
q2 = collections.deque([root.right])
while q1 and q2:
n1 = q1.popleft()
n2 = q2.popleft()
if n1 is None and n2 is None:
continue
if (n1 is None) ^ (n2 is None):
return False
if n1.val != n2.val:
return False
q1.append(n1.left)
q1.append(n1.right)
q2.append(n2.right)
q2.append(n2.left)
if not (q1 and q2):
return True
return False
открытый класс SymmetricTree {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] array = {1,2,2,3,4,4,3};
/*
* 1
* / \
* / \
* / \
* 2 2
* / \ / \
* / \ / \
* 3 4 4 3
*
* */
//int[] array = {1,2};
BinaryTree bt=new BinaryTree();
bt.data=1;
bt.left = new BinaryTree(2);
bt.right = new BinaryTree(2);
bt.left.right = new BinaryTree(3);
bt.right.right = new BinaryTree(3);
//bt=BinaryTree.buildATree(bt, array);
System.out.print(isSymmetric(bt));
BinaryTree.inOrderTraversal(bt);
}
public static boolean isSymmetric(BinaryTree root){
if(root==null)
return true;
return isSymmetricLR(root.left,root.right);
}
public static boolean isSymmetricLR(BinaryTree left, BinaryTree right){
if(left == null && right == null)
return true;
if(left!=null && right!=null)
return (left.data == right.data) &&
(isSymmetricLR(left.left, right.right)) &&
(isSymmetricLR(left.right, right.left));
return false;
}
}
Если кому-то нужна версия Swift, здесь одна.
Другим подходом было бы просто инвертировать одно из поддеревьев и сравнить два результирующих поддерева простым способом.
func compareTrees(left: TreeNode?, right: TreeNode?) -> Bool {
var res = false
if left == nil && right == nil {return true}
if left != nil && right != nil {
res = left!.val == right!.val &&
compareTrees(left!.left, right: right!.left) &&
compareTrees(left!.right, right: right!.right)
}
return res
}
func invertTree(node: TreeNode?) {
if node == nil {return}
var tmp = node!.left
node!.left = node!.right
node!.right = tmp
invertTree(node!.left)
invertTree(node!.right)
}
// and run it as:
if root == nil {print("Y")}
invertTree(root!.right)
compareTrees(root!.left, right: root!.right) ? print("Y") : print("N")
Я не очень опытен (всего год на корпоративном), но, на мой взгляд, это можно решить, используя S = рекурсия
Например:
MYTREECLASS B1= new MYTREECLASS();
MYTREECLASS B2= new MYTREECLASS();
B1= OriginalTree;
B2=OriginalTRee;
Boolean CHECK(MYTREECLASS, MYTREECLASS)
{
if (B1.Node = B2.Node)
then (
CHECK(B1.Left, B2.Right);
CHECK(B1.Right,B2.Left)
)
elseIf(b1.Left==null or b2.right...blah blah ,,)
return False)
else return False,
Возвращает true, если оно соответствует.