检查二叉树是镜像还是对称 [英] Check if a binary tree is a mirror image or symmetric

问题描述

如果一棵树是对称的，那么用于测试的基本算法是什么？因为它是一个二叉树，我会假设这将是一个递归定义的排序

What is the basics algorithm for testing if a tree is symmetrical. Because it is a binary tree, I would assume that it would be a recursive definition of sorts

正式问题如下：

如果二进制树的左右子树是相同的镜像，即二叉树是对称的，二叉树就是自己的镜像。
这是最好的解释与几个例子。

A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.

  1
 / \
2   2

TRUE

   1
  / \
 2   2
  \
   3

FALSE

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

TRUE

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

FALSE

       1
     /   \
    2     2
   /       \
  3         3

TRUE

在选择的编程语言中，定义一个BTree类/ C结构体和相关联的方法来检查树是镜像。对于静态类型语言，您可以假设节点值都是整数。

In a programming language of choice, define a BTree class/C struct and an associated method to check if the tree is a mirror image. For statically typed languages, you can assume that node values are all integers.

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

假设树的根由调用者跟踪，函数isMirror（）被调用就可以了。

Assume that the root of the tree is tracked by caller and function isMirror() is invoked on it.

另外，如果定义一个类，请确保提供一个无参数的构造函数和getter / setter方法，如果数据元素不可公开访问。 / p>

Also, if defining a class, make sure to provide a no-argument constructor and getter/setter methods if data elements are not publicly accessible.

推荐答案

如何在以下函数上调用mirrorEquals（root.left，root.right）： -

How about calling mirrorEquals(root.left, root.right) on the following function :-

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

基本上比较左子树和倒置右子树，绘制一个虚数倒数跨基地。

Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.

这篇关于检查二叉树是镜像还是对称的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！