java - 检查二叉树是否具有相同的结构

Question

我应该使用递归检查二叉树是否与另一棵树具有相同的结构。我遇到麻烦的部分是弄清楚如何在每个级别检查是否有左侧或右侧并将其与另一棵树进行比较。任何形式的帮助将不胜感激。

public  boolean hasSameStructureAs(BinaryTree tree){
     //If left and right are null they are still similar
    if(leftChild == null && rightChild == null);
        return true;
    if (leftChild == null && rightChild != null)
        return false;
    if (leftChild != null && rightChild == null){
        return false;

//我在处理下面代码的递归部分时遇到了问题，我想我已经部​​分正确了

    if (!tree.equals(rightChild.left,leftChild.left )) return false;
    if (!tree.equals(rightChild.right, leftChild.right)) return false;

    return true;

这里是一些构造函数和get/set方法。

 public class BinaryTree {
private String data;
private BinaryTree leftChild;
private BinaryTree rightChild;

public BinaryTree(String d) {
    data = d;
    leftChild = null;
    rightChild = null;
}

public BinaryTree(String d, BinaryTree left, BinaryTree right) {
    data = d;
    leftChild = left;
    rightChild = right;
}

public String getData() {
    return data;
}

public BinaryTree getLeftChild() {
    return leftChild;
}

public BinaryTree getRightChild() {
    return rightChild;}

Answer 1

您的 BinaryTree 是一个递归数据结构，因此您可以按照编写递归函数时的常用方法递归地进行检查 - 假设它已经编写。

这就是我的意思:假设您的 BinaryTree 类有一个有效的 hasSameStructureAs 方法，您只能在子节点上使用该方法。您将如何使用它检查当前节点？

• 再次检查 tree.getLeftChild() 的左子树和 this.leftChild；如果 hasSameStructureAs 返回 false，则也返回 false。如果两个左子树都是null，继续检查
• 再次检查 tree.getRightChild() 和 this.rightChild 的右子树；如果 hasSameStructureAs 返回 false，则也返回 false。如果两个右子树都为 null，或者 hasSameStructureAs 返回 true，则也返回 true。

就是这样 - 你已经完成了!您的方法需要做的就是 null 检查其左右子树，并对它们调用 hasSameStructureAs。