当前位置： 文江博客话题详情

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

发布于 2024-12-20 01:48:05 字数 803 浏览 3 评论 0原文

测试树是否对称的基本算法是什么？因为它是一棵二叉树，所以我假设它是排序的递归定义

正式问题如下：

如果二叉树的左子树和右子树是相同的镜像，则二叉树是自身的镜像，即二叉树是对称的。 通过几个例子可以最好地解释这一点。

  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 结构和关联的方法来检查树是否是镜像。对于静态类型语言，您可以假设节点值都是整数。

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

假设调用者跟踪树的根并在其上调用函数 isMirror()。

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

原文

What is the basic 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

The formal question is below:

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

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

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

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（17）

注定孤独终老 2024-12-27 01:48:06

java脚本解决算法怎么样

使用

araay = ["10" , "2", "2", "#", "1", "1", "#"]
让我们将其分解为每个步骤，

step 1 = ["10"]
step 2 = [ "2", "2" ]
step 3 = ["#", "1", "1", "#"]

检查除第一步之外的每个步骤的镜像，

让我们执行步骤 3 。
第 3 步 = ["#", "1", "1", "#"]
从中间将其分成 2 个数组

step 3 1 = ["#", "1" ]
step 3 2 = ["1", "#"]

现在反转步骤 3 2

step 3 2 = ["1", "#"]

现在检查步骤 3 2 是否等于步骤 3 1

对每个步骤执行上述操作，

如果所有步骤都是镜像，则二叉树是镜像

const Input = ["10" , "2", "2", "#", "1", "1", "#"];
function isEqual(a,b)
{
  // if length is not equal
  if(a.length!=b.length)
   return false;
  else
  {
  // comapring each element of array
   for(var i=0;i<a.length;i++)
   if(a[i] !== b[i]){
    return false;
   }
    return true;
  }
}

// Response 
let symetric = true ;
let stepSymetric = true ;
let mirror = true ;
// length of input 
const length = Input.length ;
// const length = 31 ;

// lets create binary tree from it

const totalSteps =
      Math.log(length + 1)/Math.log(2) ;

// check for symetric binary tree
function checkInt(n) { return parseInt(n) === n };
 symetric = checkInt(totalSteps);

//now check for mirror
let goneArrayLength = 0 ;
for (let i = 0; i < totalSteps; i++) { 
  const cStep = Math.pow(2,i);
  
  const stepArray = [];
  // console.log(goneArrayLength);
  
  // now update the step array 
  const start = goneArrayLength ;
  const end =  goneArrayLength + cStep ;
  
  for (let j = start; j < end; j++) {
    stepArray.push(Input[j])
  }
  
  console.log(stepArray);
  // Now we have each step lets find they are mirror image or not
  // check for even length
  if(stepArray.length%2 !== 0 && i !== 0){
    stepSymetric = false ;
  }
  const partitation = stepArray.length / 2 ;
  const leftArray = stepArray.slice(0,partitation);
  const rightArray = stepArray.slice(partitation , partitation * 2);
  // console.log("leftArray");
  // console.log(leftArray);
  // console.log("rightArray");
  // console.log(rightArray);
  function mirrorCheck (){
    let check = false;
    if(cStep === 1){
      return true ;
    }
    let array1 = leftArray;
    let array2 = rightArray.reverse();
    // console.log("first");
    // console.log(array1);
    // console.log("second");
    // console.log(array2);
   let equal = isEqual(array1 , array2)
   // console.log(equal);
    check = true ;
    if(!equal){
      // console.log("Noooooooooooooooo")
      check = false ;
    }
    
    return check;
  }
  let mirrorC = mirrorCheck();
  
  if(!mirrorC){
    mirror = false;
  }
  goneArrayLength = goneArrayLength + cStep ;
}
console.log(mirror + " " + symetric + " " + stepSymetric )

if(mirror && symetric && stepSymetric ){
  console.log("Mirror Image");
  
}
else{
  console.log("Not mirror image")
}
// console.log(isSymetric);
// console.log(totalSteps);

how about a java script solution

algorithm used

araay = ["10" , "2", "2", "#", "1", "1", "#"]
lets break this into each step

step 1 = ["10"]
step 2 = [ "2", "2" ]
step 3 = ["#", "1", "1", "#"]

check mirror for each step other than first step

lets take step 3 .
step 3 = ["#", "1", "1", "#"]
break this into 2 array from middle

step 3 1 = ["#", "1" ]
step 3 2 = ["1", "#"]

Now reverse step 3 2

step 3 2 = ["1", "#"]

now check if step 3 2 is equal to step 3 1

Do the above thing for each step

if all are mirror then binary tree is mirror

const Input = ["10" , "2", "2", "#", "1", "1", "#"];
function isEqual(a,b)
{
  // if length is not equal
  if(a.length!=b.length)
   return false;
  else
  {
  // comapring each element of array
   for(var i=0;i<a.length;i++)
   if(a[i] !== b[i]){
    return false;
   }
    return true;
  }
}

// Response 
let symetric = true ;
let stepSymetric = true ;
let mirror = true ;
// length of input 
const length = Input.length ;
// const length = 31 ;

// lets create binary tree from it

const totalSteps =
      Math.log(length + 1)/Math.log(2) ;

// check for symetric binary tree
function checkInt(n) { return parseInt(n) === n };
 symetric = checkInt(totalSteps);

//now check for mirror
let goneArrayLength = 0 ;
for (let i = 0; i < totalSteps; i++) { 
  const cStep = Math.pow(2,i);
  
  const stepArray = [];
  // console.log(goneArrayLength);
  
  // now update the step array 
  const start = goneArrayLength ;
  const end =  goneArrayLength + cStep ;
  
  for (let j = start; j < end; j++) {
    stepArray.push(Input[j])
  }
  
  console.log(stepArray);
  // Now we have each step lets find they are mirror image or not
  // check for even length
  if(stepArray.length%2 !== 0 && i !== 0){
    stepSymetric = false ;
  }
  const partitation = stepArray.length / 2 ;
  const leftArray = stepArray.slice(0,partitation);
  const rightArray = stepArray.slice(partitation , partitation * 2);
  // console.log("leftArray");
  // console.log(leftArray);
  // console.log("rightArray");
  // console.log(rightArray);
  function mirrorCheck (){
    let check = false;
    if(cStep === 1){
      return true ;
    }
    let array1 = leftArray;
    let array2 = rightArray.reverse();
    // console.log("first");
    // console.log(array1);
    // console.log("second");
    // console.log(array2);
   let equal = isEqual(array1 , array2)
   // console.log(equal);
    check = true ;
    if(!equal){
      // console.log("Noooooooooooooooo")
      check = false ;
    }
    
    return check;
  }
  let mirrorC = mirrorCheck();
  
  if(!mirrorC){
    mirror = false;
  }
  goneArrayLength = goneArrayLength + cStep ;
}
console.log(mirror + " " + symetric + " " + stepSymetric )

if(mirror && symetric && stepSymetric ){
  console.log("Mirror Image");
  
}
else{
  console.log("Not mirror image")
}
// console.log(isSymetric);
// console.log(totalSteps);

回复 原文
做个ˇ局外人 2024-12-27 01:48:06
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def is_mirror(t1,t2):
            # this is when I hit the leaf nodes
            if t1 is None and t2 is None:
                return True
            # if node has only one child
            if t1 is None or t2 is None:
                return False
            return t1.val==t2.val and is_mirror(t1.left,t2.right) and is_mirror(t1.right,t2.left)
        return is_mirror(root.left,root.right)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def is_mirror(t1,t2):
            # this is when I hit the leaf nodes
            if t1 is None and t2 is None:
                return True
            # if node has only one child
            if t1 is None or t2 is None:
                return False
            return t1.val==t2.val and is_mirror(t1.left,t2.right) and is_mirror(t1.right,t2.left)
        return is_mirror(root.left,root.right)
回复 原文
翻了热茶 2024-12-27 01:48:06

我经验不是很丰富（在公司工作了一年），但在我看来，这可以通过使用 S=recursion 来解决

例如：

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。

I'm not very experienced (just a year at corporate), but in my opinion, this can be solved by using S=recursion

For example:

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,

Return true if it matches.

回复 原文
一曲琵琶半遮面シ 2024-12-27 01:48:05

如何在以下函数上调用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);
}

基本上比较左子树和反转右子树，在根上绘制一条假想的反转线。

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.

回复 原文
薆情海 2024-12-27 01:48:05

解决方案 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;
}

Solution 1 - Recursively:

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

Solution 2 - Iteratively:

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;
}
回复 原文
剩余の解释 2024-12-27 01:48:05

使用上述方法的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作为队列 em>

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

Recursive and Iterative solutions in Java using approaches discussed above

Recursive

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

Iterative using LinkedList as a Queue

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 Case

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

Tree Node class

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;
}
}
回复 原文
听，心雨的声音 2024-12-27 01:48:05

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

The recursive solution from @gvijay is very clear, and here's an iterative solution.

Inspect each row of the tree from top to bottom and see if the values are a palindrome. If they all are then, yes, it's a mirror. You'll need to implement an algorithm to visit each row and include null values for sparse trees. In pseudocode:

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

The trick is to design the algorithm to iterate the rows of a tree with consideration that sparse trees should have null values as place holders. This Java implementation seems ok:

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;
  }
}
回复 原文
ま昔日黯然 2024-12-27 01:48:05

编辑

正如评论中所指出的，我的算法的第一个版本对于某些输入失败了。我不会重新发明轮子，我只会使用 @gvijay 正确的算法提供一个 Python 答案。首先，二叉树的表示：

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

EDIT

As was pointed out in the comments, my first version of the algorithm failed for certain inputs. I'm not going to reinvent the wheel, I'll just provide a Python answer using @gvijay correct algorithm. First, a representation for the binary tree:

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

I tested the above code using all the sample trees in the question and the trees which were returning incorrect results, as mentioned in the comments. Now the results are correct for all cases:

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
回复 原文
何以畏孤独 2024-12-27 01:48:05

这是 gvijay 的 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 );
}

Here is a C++ solution per 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 );
}
回复 原文
苯莒 2024-12-27 01:48:05

下面是关于 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;
}

Below is the solution with respect to 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;
}
回复 原文
鸢与 2024-12-27 01:48:05

如果有人需要 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")

If someone needs a Swift version, here's one.

Another approach would be to just invert one of the subtrees, and compare the two resulting subtrees in a straightforward manner.

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")
回复 原文
一杆小烟枪 2024-12-27 01:48:05

方法略有不同。

如何对二叉树进行中序遍历，将所有内容存储在某些数据结构（如字符串/数组）中。

遍历完成后，检查数组中的元素是否形成回文。
空间效率不高（递归需要 O(log(n))，此方法的时间复杂度为 O(n)），但这也可以。

Slightly different approach.

How about do an inorder traversal of the binary tree storing all the contents in some data structure like a string/ array.

Once traversal is complete, check if the elements in your array form a palindrome.
Not as efficient space wise (recursion takes O(log(n)), this method tales O(n)) but this will work as well.

回复 原文
凑诗 2024-12-27 01:48:05

在 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

Iterative solution using slightly different approach in python. Use queue1 to store left children in order of left to right and queue2 to store right children in order of right to left and compare for equality.

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
回复 原文
打小就很酷 2024-12-27 01:48:05

使用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)

using 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)
回复 原文
梦途 2024-12-27 01:48:05

我想我会在 Python 中添加一个解决方案，有些人可能会发现它比其他方法更容易理解。这个想法是：

  1. 将 +1 添加到左孩子返回的值中。
  2. 将 -1 添加到右子节点返回的值中。
  3. 将l+r 返回给父级

因此，如果树中的任何节点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

Thought I'd add a solution in Python that some people might find easier to understand than other approaches. The idea is:

  1. add +1 to value returned by left child.
  2. add -1 to value returned by right child.
  3. return l+r to parent

So if l+r == 0 for any node in the tree, then the sub-tree anchored at that node is symmetric. Therefore the entire tree is symmetric only if l+r == 0 at root.

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
回复 原文
不气馁 2024-12-27 01:48:05
public class 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;
    }
}

public class 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;
    }
}
回复 原文
奢望 2024-12-27 01:48:05

使用队列，因为我发现递归有点难。

bool isSymmetric(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    q.push(root);
    while(q.empty()==false){
        TreeNode* a = q.front();
        q.pop();
        TreeNode* b = q.front();
        q.pop();
        if(a->val != b->val){
            return false;
        }
         if(a->left == nullptr and b->right != nullptr)
            return false;
        if(a->left != nullptr and b->right == nullptr)
            return false;
        if(a->right != nullptr and b->left == nullptr)
            return false;
        if(a->right == nullptr and b->left != nullptr)
            return false;
        if(a->left != nullptr and b->right != nullptr){
            q.push(a->left);
            q.push(b->right); 
        }
        if(a->right != nullptr and b->left != nullptr){
            q.push(a->right);
            q.push(b->left);
        }`enter code here`
    }
    return true;
}

Using Queue , Because i find Recursion a bit hard.

bool isSymmetric(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    q.push(root);
    while(q.empty()==false){
        TreeNode* a = q.front();
        q.pop();
        TreeNode* b = q.front();
        q.pop();
        if(a->val != b->val){
            return false;
        }
         if(a->left == nullptr and b->right != nullptr)
            return false;
        if(a->left != nullptr and b->right == nullptr)
            return false;
        if(a->right != nullptr and b->left == nullptr)
            return false;
        if(a->right == nullptr and b->left != nullptr)
            return false;
        if(a->left != nullptr and b->right != nullptr){
            q.push(a->left);
            q.push(b->right); 
        }
        if(a->right != nullptr and b->left != nullptr){
            q.push(a->right);
            q.push(b->left);
        }`enter code here`
    }
    return true;
}
回复 原文
~没有更多了~

关于作者

白日梦

暂无简介

文章
评论
25 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

知足的幸福

文章 0 评论 0

我一向站在原地

文章 0 评论 0

慕烟庭风

文章 0 评论 0

秉忠贞之诚 守退让之实

文章 0 评论 0

小兔几

文章 0 评论 0

mb_3y7WUgWY

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文