一棵树的值与另一棵树相匹配。

Question

我正在解决一些关于树木的问题，为科技面试做准备。我偶然发现了一个问题，看看一个树(子集)的值是否与另一个树(主树)的值相匹配。

为例

          3     is part of                4  
         / \    ----------->             / \
        7   9                           3   7
                                           / \
                                          8   9

我想出了下面的解决方案。

public static boolean isSubset(TreeNode<String> subNode, TreeNode<String> mainNode){
    if(subNode == null)     
        return true;

    if(mainNode == null)
        return false;

    if(subNode.data.equals(mainNode.data)){
        return (isSubset(subNode.left,mainNode) && isSubset(subNode.right,mainNode));
    }else{
        return (isSubset(subNode,mainNode.left) || isSubset(subNode,mainNode.right)); 
    }
}

但是，此解决方案只检查节点是否与mainTree中的节点顺序相同(根、左和右)。我应该在上面的代码中更改什么，这样我就可以用主树的每个节点来检查我的子树中的每个节点是否匹配？

Answer 1

如果我理解您的需求，您根本不关心树结构；您只需要测试植根于subNode的树的每个元素是否存在于植根于mainNode的树中。我建议您开发一个谓词(让我们称之为contains)来测试单个值是否在树中。然后你可以在此基础上：

public static boolean isSubset(TreeNode<String> subNode, TreeNode<String> mainNode){
    if(subNode == null)     
        return true;

    if(mainNode == null)
        return false;

    return mainNode.contains(subNode.data)
        && isSubset(subNode.left, mainNode)
        && isSubset(subNode.right, mainNode);
}