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

Question

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

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

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

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

Answer 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);
}

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

Answer 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;
}

Answer 3

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

Узел дерева класс

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;
}
}

Answer 4

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

Answer 5

Вот решение C ++ за гвиджей

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 );
}

Answer 6

EDIT

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

Answer 7

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

Answer 8

Ниже приведено решение относительно C-кода

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;
}

Answer 9

Думаю, я бы добавил в Python решение, которое некоторым людям будет легче понять, чем другим подходам.Идея такова:

1. добавить +1 к значению, возвращенному левым потомком.
2. добавить -1 к значению, возвращенному правым потомком.
3. return l+r to parent

Так что, если l+r == 0 для любого узла в дереве, то поддерево, привязанное к этому узлу, является симметричным.Поэтому все дерево симметрично, только если l+r == 0 в корне.

def check(root):
    l = check(root.left)+1 if root.left else 0
    r = check(root.right)-1 if root.right else 0
    return l+r

def is_symmetric(root):
    return root is not None and check(root) == 0

Answer 10

с использованием Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(root1, root2):
            if not root1 and not root2: return True
            if not root1 or not root2: return False            
            if root1.val != root2.val: return False
            if helper(root1.left, root2.right): return helper(root1.right, root2.left)
            return  False
        return helper(root, root)