Проверьте, является ли двоичное дерево зеркальным или симметричным - PullRequest
Новая
       70

Проверьте, является ли двоичное дерево зеркальным или симметричным

50 голосов
/ 08 декабря 2011

Каков основной алгоритм проверки, если дерево симметрично.Поскольку это бинарное дерево, я бы предположил, что это будет рекурсивное определение сортов

Формальный вопрос приведен ниже:

Бинарное дерево - это зеркальное отражение самого себя, если его оставить иправые поддеревья - это идентичные зеркальные изображения, т. е. двоичное дерево симметрично.Это лучше всего объяснить несколькими примерами. 

  1
 / \
2   2

ИСТИНА 

   1
  / \
 2   2
  \
   3

ЛОЖЬ 

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

ИСТИНА 

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

ЛОЖЬ 

       1
     /   \
    2     2
   /       \
  3         3

TRUE

На выбранном языке программирования определите структуру класса BTree / C и связанный метод, чтобы проверить, является ли дерево зеркальным отображением.Для языков со статической типизацией можно предположить, что все значения узлов являются целыми числами. 

Class/structure definition
BTree {
  BTree left;
  BTree right;
  int value;
}

Предположим, что корень дерева отслеживается вызывающей стороной и для него вызывается функция isMirror ().

Кроме того, при определении класса обязательно предоставьте конструктор без аргументов и методы getter / setter, если элементы данных не являются общедоступными.

Ответы [ 14 ]

0 голосов
/ 30 июля 2015

открытый класс 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;
}

}

0 голосов
/ 22 ноября 2014

Итеративное решение с использованием немного другого подхода в 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
0 голосов
/ 20 ноября 2013

Немного другой подход.

Как насчет обхода по порядку двоичного дерева, хранящего все содержимое в некоторой структуре данных, такой как строка / массив.

По завершении обхода проверьте, образуют ли элементы в вашем массиве палиндром. Не так эффективно в пространстве (рекурсия требует O (log (n)), этот метод рассказывает о O (n)), но это также будет работать.

0 голосов
/ 27 февраля 2013

Я не очень опытный (всего год в корпоративном), но, на мой взгляд, это можно решить с помощью 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, если оно совпадает.

Страница:
...