java - 二叉树奇数节点之和

Question

我想知道所有奇数节点的总和，并以递归方式对其进行编程。但我无法让它工作，所以也许你们可以帮助我......

这是我的 BinNode 类

package com.company;

public class BinNode {
  public int element;
  public BinNode left, right;


public BinNode(int e, BinNode l, BinNode r) {
    element = e;
    left = l;
    right = r;
}

public BinNode(int e) {
    element = e;
    left = null;
    right = null;
  }
 }

现在我的方法首先检查树是否为空，否则如果不是则调用递归方法

public int countOdd() {
    if(root == null) {
        return 0;
    }
    return countOdd_rek(root);
}

现在是方法

private int countOdd_rek(BinNode bn) {
    int odd, oddRight, oddLeft;
    odd = oddRight = oddLeft = 0;

    if(bn.left != null) {
        if(bn.left.element % 2 != 0) { //add +1 if bn.left is odd
            oddLeft +=1;
        }
        countOdd_rek(bn.left);
    }

    if(bn.right != null) {
        if(bn.right.element % 2 != 0) { //add +1 if bn.right is odd
            oddRight +=1;
        }
        countOdd_rek(bn.right);
    }

    //add +1 if root is also odd
    if(bn.element % 2 != 0)
        odd = 1 + oddLeft + oddRight;

    //add nothing if root isnt odd
    if(bn.element % 2 == 0)
        odd = 0 + oddLeft + oddRight;
    return odd;
}

也许有人可以帮忙，那就太好了......谢谢

编辑我解决了解决方案:

private int countOdd_rek(BinNode bn) {
    int odd, oddRight, oddLeft;
    odd = oddRight = oddLeft = 0;

    if(bn.left != null) {
            oddLeft += countOdd_rek(bn.left);
    }

    if(bn.right != null) {
            oddRight += countOdd_rek(bn.right);
    }

    //add +1 if root is also odd
    if(bn.element % 2 != 0)
        odd = 1 + oddLeft + oddRight;

    //add nothing if root isnt odd
    if(bn.element % 2 == 0)
        odd = 0 + oddLeft + oddRight;


    return odd;
}

Answer 1

您的主要问题是您实际上没有对 countOdd_rek(...) 的值执行任何操作。此外，您还定义了局部变量来存储奇数计数，这些奇数计数将在每次递归方法调用时被覆盖。一个更简洁的方法是这样的:

public class BinNode {
    public int element;
    public BinNode left, right;


    public BinNode(int e, BinNode l, BinNode r) {
        element = e;
        left = l;
        right = r;
    }

    public BinNode(int e) {
        element = e;
        left = null;
        right = null;
    }

    public static int countOdd(BinNode root) {
        return countOdd_rek(root);
    }

    private static int countOdd_rek(BinNode bn) {
        if (bn == null) {
            return 0;
        }


        if (bn.element % 2 != 0) {
            //add +1 if root is also odd
            return 1 + countOdd_rek(bn.left) + countOdd_rek(bn.right);
        } else {
            return countOdd_rek(bn.left) + countOdd_rek(bn.right);
        }
    }

    public static void main(String[] args) {
        BinNode root = new BinNode(1,
                new BinNode(2,
                        new BinNode(4, null, null),
                        new BinNode(5, null, null)),
                new BinNode(3,
                        new BinNode(6, null, null),
                        new BinNode(7, null, null)));

        System.out.println(countOdd(root));
    }
}

我也在 main 方法中为您添加了一个示例。

如果您有任何疑问，请告诉我。

编辑:刚刚看到你自己解决了这个问题。干得好——我想你可以看看我的代码作为引用。