为什么会得到与预期相反的结果?

问题描述 投票:1回答:2

我写了一个代码来判断小二叉树t1是否是t2的子树。我应该得到true作为结果,但我得到相反的结果。

这是我的代码:

class Node {
    int val;
    Node left, right;
    public Node(int v) {
        val = v;
        left = right = null;
    }
}
public class BT {
    Node root;
    public BT() {
        root = null;
    }
    public boolean containsTree(Node t1, Node t2) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        getOrderString(t1, s1);
        getOrderString(t2, s2);
        return s1.indexOf(s2.toString()) != -1;
    }
    public void getOrderString(Node t, StringBuilder s) {
        if (t == null) {
            s.append("X");
            return;
        }
        s.append(t.val);
        getOrderString(t.left, s);
        getOrderString(t.right, s);
    }
    public static void main(String[] args) {
        BT bt = new BT();
        bt.root = new Node(10);
        bt.root.left = new Node(12);
        bt.root.right = new Node(15);
        bt.root.left.left = new Node(25);
        bt.root.left.right = new Node(30);
        bt.root.right.left = new Node(36);
        BT bt2 = new BT();
        bt2.root = new Node(10);
        bt2.root.left = new Node(12);
        bt2.root.right = new Node(15);
        bt2.root.left.left = new Node(25);
        System.out.println(bt.containsTree(bt.root, bt2.root));
    }
}

有人可以向我解释为什么我变得虚假吗?

java binary-tree subtree
2个回答
0
投票

您用于构造树的API很难阅读。如果定义了构造函数:

public Node(int v, Node left, Node right)

然后您可以将树声明为:

bt.root = new Node(
    10,
    new Node(
        12,
        new Node(25, null, null),
        new Node(30, null, null)),
    new Node(
        25,
        new Node(36, null, null),
        null));

bt2.root = new Node(
    10,
    new Node(
        12,
        new Node(25, null, null),
        null)),
    new Node(15, null, null));

类似,我认为很容易看到第二个不是第一个的子树:

  • 第一个中值为10的节点具有值为25的右节点;在第二个中,它的正确值为15;
  • 第一个值为12的节点具有非空的右值,而第二个值为null。

0
投票

第二棵树不是第一棵树的子树。这就是为什么它返回false的原因,因此您的代码实际上是正确的:)

First and Second Trees

© www.soinside.com 2019 - 2024. All rights reserved.