功能：这个二叉查找树是"odd balanced"吗？

Question

如果左边的奇数后代数==右边的奇数后代数，则树为"odd balanced"。

public boolean isOddBalanced() {   
    return (isOddBalanced (root) >= 0);
}
private int isOddBalanced (Node x) {
    if (x == null) return 0;
    int ls = isOddBalanced (x.left);
    int rs = isOddBalanced (x.right);
    if (Math.abs (ls - rs) > 0) return -1;
    else return 0;
}

我卡在了如何计算和比较每一侧奇数键的数量上。任何见解将不胜感激。

尝试实现@nem 的想法：

public boolean isOddBalanced() {   
    return (isOddBalanced (root, '0') >= 0);
}
private int isOddBalanced (Node x, char side) {
    int count = 0;
    if (x == null) return 0;
    count = isOddBalanced (x.left, 'l');
    count = isOddBalanced (x.right, 'r');
    if (x.key % 2 != 0 && side == 'l') count += 1;
    if (x.key % 2 != 0 && side == 'r') count -= 1;
    if (count != 0) return -1;
    else return 0;
}

Answer 1

看看这个。

private int countNode(Node x){
    if(x == null) return 0;
    else return countNode(x.left) + countNode(x.right) + 1;
}

private bool isOddBalanced(Node x){
    int ls = countNode(x.left);
    int rs = countNode(x.right);
    return (ls == rs);
}

Answer 2

你缺少的是一种通过递归计算奇值节点的方法。

您可以使用包装器 class 实现此目的（因为 Java 是 pass-by-value）：

class OddCounter {
    int count = 0;
}

现在你可以做什么，而不是分别计算左或右奇值节点，你可以每次找到左奇值节点时在count上加1并从中减去1 count 每次找到一个右奇值节点。这意味着，如果树是奇数平衡的，count 变量将为 0。

您的代码将如下所示：

public boolean isOddBalanced() { 
    OddCounter c = new OddCounter();  
    isOddBalancedHelper(root, c, '0');
    return (c.count == 0);
}

private void isOddBalancedHelper (Node x, OddCounter c, char comingFrom) {
    if (x == null) return;
    isOddBalancedHelper(x.left, c, 'l');  
    isOddBalancedHelper(x.right, c, 'r'); 
    if(x.value % 2 != 0 && comingFrom == 'l') {        // if current node is odd and a left child
        c.count++;
    } else if(x.value % 2 != 0 && comingFrom == 'r') { // if current node is odd and a right child
        c.count--;
    }
}

根据您的评论编辑（不使用任何额外的 classes 或函数）

你可以做的是使用实例变量而不是计数器class:

int oddCount;                       // use an instance variable to count the difference between the amount of left odd-nodes and right odd-nodes

public boolean isOddBalanced() { 
    this.oddCount = 0;              // reset count each time balance is calculated to ensure answer is correct each time (and not just on the first call)
    isOddBalancedHelper(root, '0');
    return (this.oddCount == 0);
}

private void isOddBalancedHelper (Node x, char comingFrom) {
    if (x == null) return;
    isOddBalancedHelper(x.left, 'l');  
    isOddBalancedHelper(x.right, 'r'); 
    if(x.value % 2 != 0 && comingFrom == 'l') {        // if current node is odd and a left child
        this.oddCount++;
    } else if(x.value % 2 != 0 && comingFrom == 'r') { // if current node is odd and a right child
        this.oddCount--;
    }
}

您可以做的另一项改进是兑现 oddCount 的值，并且仅在树内容以任何方式更改时更新它（节点为 added/removed，节点值已更改）。

这将允许您对每个树结构仅计算一次 isOddBalanced() 的值。

Answer 3

既然你想知道左边奇数后代的数量==右边奇数后代的数量，你只需要左右孩子之间的差异。

public boolean isOddBalanced() {   
    return (CountChilds(root.left) == CountChilds(root.right));
}
private int CountChilds(Node x) {
    if (x == null) return 0;
    // left childs + right childs + me
    else return CountChilds(x.left) + CountChilds(x.right) + 1; 
}

Answer 4

你的问题似乎有问题。

If the number of odd descendents on the left == number of odd descendents on the right, the tree is "odd balanced".

这意味着你需要比较根节点左奇数后代的数量和根节点右奇数后代的数量。然而，这不是定义树属性的常用方法——这些属性通常是为树中的 每个节点 定义的。这意味着您需要检查树的每个节点的奇数平衡。

你可以在遍历整个树的单个递归过程中做到这一点，就像@nem 说的那样。但是您可以稍微改进解决方案。

注意，一旦我们将奇平衡定义为递归属性，那么如果它的任何子树不平衡，树就不会是奇平衡的。因此，在循环的同时，我们可以检索余额中奇数节点数和的信息。如果没有两个结果的复合容器，我们怎么能做到这一点？那么，如果一个子树是不平衡的，整棵树都是不平衡的，对吧？所以我们已经知道整棵树是不平衡的，因此不需要有关节点数量的信息。因此，我们可以 return 这些相互排斥的信息片段作为单个 int 值：对于 odd–balanced 子树中奇数节点的数量为零或正数，或者不平衡子树为负。

private int isOddBalanced (Node x) {
    // empty tree is balanced and it contains no odd nodes
    if (x == null) return 0;

    // check subtrees; if any is unbalanced, return the status up the tree
    int ls = isOddBalanced (x.left);
    // don't test the right subtree if the left one is unbalanced
    if (ls < 0) return -1;

    int rs = isOddBalanced (x.right);
    if (rs < 0) return -1;

    // when both are balanced test for odd-nodes numbers equality
    if (ls != rs) return -1;

    // return the current sub-total
    return ls + rs + ((x.key % 2 == 0) ? 0 : 1);
}

功能：这个二叉查找树是"odd balanced"吗？

Function: is this binary search tree "odd balanced"?

java

recursion

binary-search-tree