检查二叉树是镜像还是对称

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

真正

在选择的编程语言中,定义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 实现看起来没问题：

boolean isMirror(BTree tree) {
  foreach (List<Integer> row : tree.rows() {
    if (row != row.reverse()) return false;
  }
  return true;
}