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

testing树是否对称的基本algorithm是什么？ 因为它是一棵二叉树，所以我会假定它是一个recursion的sorting定义

正式的问题如下：

如果其左右子树是相同的镜像，即二叉树是对称的，则二叉树是其自身的镜像。 最好用几个例子来解释。

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 

真正

在select的编程语言中，定义BTree类/ C结构和相关联的方法来检查树是否是镜像。 对于静态types语言，可以假定节点值都是整数。

 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

解决scheme1 ​​ – recursion地：

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

解决scheme2 – 迭代地：

 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

@gvijay的recursion解决scheme非常清晰，这里是一个迭代的解决scheme。

检查树的每一行从上到下，看看这些值是否是回文。 如果他们都是的话，是的，这是一面镜子。 您需要实现一个algorithm来访问每一行，并为稀疏树包含空值。 在伪代码中：

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

诀窍是devisealgorithm迭代树的行，考虑到稀疏树应该有空值作为占位符。 这个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 4

使用上面讨论的方法在Java中recursion和迭代解决scheme

recursion

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

testing用例

  @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 5

编辑

正如在评论中指出的那样，我的第一版algorithm在某些input方面失败了。 我不打算重新发明轮子，我只是提供一个使用@gvijay正确algorithm的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)) 

我使用问题中的所有示例树和返回错误结果的树来testing上述代码，如注释中所述。 现在结果对于所有情况都是正确的：

 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 6

这是每个gvijay的C ++解决scheme

 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 7

以下是关于C-COde的解决scheme

 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 8

略有不同的做法。

那么如何遍历二叉树来存储某些数据结构中的所有内容，如string/数组。

遍历完成后，检查数组中的元素是否形成回文。 没有效率的空间明智（recursion需要O（log（n）），这个方法故事O（n）），但是这也将工作。

Answer 9

在Python中使用稍微不同的方法迭代解决scheme。 使用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 

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

}

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

Answer 12

我不是很有经验（只有一年在公司），但在我看来，这可以通过使用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。