验证给定级别的所有节点在二叉树中是否具有不同的值

Question

我的问题是，如果不使用任何数据结构（堆栈、列表等），这个问题是否可以解决？还是需要一个？（如果可能的话，我也想看看这两种情况下的解决方案）。

问题：

有一个 BinaryTree class 表示包含整数值的二叉树。假设已经有实现的方法：

public BinaryTree right();  // returns right children
public BinaryTree left();   // returns left children
public int val();   // returns value of root node.

执行以下递归方法：

public static boolean allDifferentAtLevel(BinaryTree a, int lev){...}

接收整数的二叉树和 returns true 仅当 a 的节点的所有值都在level lev 都有不同的值。

提前感谢您的宝贵时间。

Answer 1

我们可以使用 HashSet<Integer> 来跟踪第 lev 级别的数据。

public static boolean allDifferentAtLevel(BinaryTree a, int lev){
    return checker(new HashSet<Integer>(),a,0,lev); //EmptySet, Root, CurrentLevel, Level
}

public static boolean checker(HashSet<Integer> set,BinaryTree a, int currentLevel, int lev) {
    if(a==null) //If current node of tree is null, return true.
        return true;

    if(currentLevel==lev) //If currentLevel is the required level, We don't need to move further.
                          //We can just validate the data at currentLevel and return the appropriate value.
    {
        int value=a.val();
        if(set.contains(value)) //If set contains the value, Duplication found.
            return false;

        set.add(value);
        return true;
    }

    //Check for both of the children.
    return checker(set,a.left(),currentLevel+1,lev) && checker(set,a.right(),currentLevel+1,lev);
}

Answer 2

是的，这可以通过递归解决，无需额外的数据结构。

让我们尝试定义 allDifferentAtLevel(BinaryTree tree, int lev) 方法对于不同的 lev 应该是什么样子：

对于 lev=0，结果只是 false，因为级别 0 上的所有节点都具有相同的值。 0 层只有一个节点，因此所有个节点具有相同的值。

对于 lev=1，检查 tree.right().val() == tree.left().val() 非常简单（添加 null 检查）。

对于更高级别 (lev>1)，您应该递归调用该方法。基本上，allDifferentAtLevel(tree.left(), lev - 1) 和 allDifferentAtLevel(tree.right(), lev - 1) 将确保左子树和右子树满足条件。不幸的是，这是不够的，因为左右子树之间可能有一些共同的价值。

但是可以解决这个问题，不仅检查左和右，还检查更深两层的子树的所有组合。类似于：

BinaryTree ll = tree.left() == null ? null : tree.left().left();
BinaryTree lr = tree.left() == null ? null : tree.left().right();
BinaryTree rl = tree.right() == null ? null : tree.right().left();
BinaryTree rr = tree.right() == null ? null : tree.right().right();

BinaryTree ll_lr = tree.left();
BinaryTree ll_rl = new BinaryTree(0, ll, rl);
BinaryTree ll_rr = new BinaryTree(0, ll, rr);
BinaryTree lr_rl = new BinaryTree(0, lr, rl);
BinaryTree lr_rr = new BinaryTree(0, lr, rr);
BinaryTree rl_rr = tree.right();

return allDifferentAtLevel(ll_lr, lev - 1) &&
       allDifferentAtLevel(ll_rl, lev - 1) &&
       allDifferentAtLevel(ll_rr, lev - 1) &&
       allDifferentAtLevel(lr_rl, lev - 1) &&
       allDifferentAtLevel(lr_rr, lev - 1) &&
       allDifferentAtLevel(rl_rr, lev - 1);

有四个子树更深两层（ll、lr、rl、rr）。但是我们不能只检查这些子树，我们必须相互检查它们。这些子树有六对不同的可能。为了相互检查这些子树，我们可以为每个不同的对创建一个二叉树（ll_lr、ll_rl、ll_rr、lr_rl、lr_rr, rl_rr) 然后递归地检查这些二叉树中的每一个。如果任何子树 ll、lr、rl、rr 在 lev-2 上有相等的元素，就会有一对子树在 lev-2 上有相等的元素lev-1.

所以是的，这个问题可以通过递归解决，不需要额外的数据结构。我不认为 BinaryTree 是一个额外的数据结构。

话虽如此，使用像集合这样的附加数据结构会使任务变得更容易。

Answer 3

这是可能的，但效率很低 - 您可以实现两个递归函数：

DFS 达到所需级别的所有节点
从第一个函数（对于所需级别的每个节点）调用另一个函数，该函数将计算（也使用 DFS）所有节点的值等于第一个函数考虑的节点的值，并检查这个count 等于 1.

验证给定级别的所有节点在二叉树中是否具有不同的值

Verify that all nodes at given level have different values in binary tree

java

algorithm

recursion

binary-tree