Подтвердить что ты не робот

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

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

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

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

  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, если элементы данных недоступны.

4b9b3361

ОТВЕТЫ

Ответ 1

Как насчет вызова 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);
}

В основном сравнить левое поддерево и инвертированное правое поддерево, вырисовывая воображаемую линию инверсии через корень.

Ответ 2

Решение 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;
}

Ответ 3

Рекурсивное решение из @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;
  }
}

Ответ 4

Рекурсивные и итеративные решения в 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;
}
}

Ответ 5

ИЗМЕНИТЬ

Как было отмечено в комментариях, моя первая версия алгоритма не удалась для определенных входов. Я не собираюсь изобретать колесо, я просто предоставляю ответ на 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

Ответ 6

Вот решение С++ на 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 );
}

Ответ 7

Ниже приведено решение относительно 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;
}

Ответ 8

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

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

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

Ответ 9

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

Ответ 10

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

}

Ответ 11

Если кому-то нужна версия 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")

Ответ 12

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