计算二叉树的右节点

Question

我想计算二叉树的正确节点，例如以下一个：

    15

   /

10

   \

    14

所以我做了以下程序：

public class NodeT {

    int elem;

    NodeT left;

    NodeT right;

    public NodeT(int elem){

        this.elem=elem;

        left=null;

        right=null;

    }

}

public class Tree {

    public NodeT createTree(){

        NodeT root=new NodeT(15);

        NodeT n1=new NodeT(10);

        NodeT n4=new NodeT(14);

        root.left=n1;

        n1.right=n4;

        return root;

    }

 public int countRight(NodeT root){

         if (root==null) return 0;    //version 1

         else{

             return 1+countRight(root.right);

         }

     }

我通过以下方式调用了我的主程序：

Tree tree=new Tree();

NodeT root=tree.createTree();

System.out.println(tree.countRight(root))

此代码打印 1 作为正确答案，但我不明白为什么会这样。对于我所看到的 15 的右分支等于 null，因此对递归函数 countRight() 的调用应该返回 0 并打印不正确的答案。

我见过其他解决方案，我发现为了计算所有节点，他们使用如下解决方案：

     static int n;

     public int countRight(NodeT root){   //version 2

         if (root==null) return 0;

         if (root.left!=null){

             n=countRight(root.left);

         }

         if (root.right!=null){

             n++;

             n=countRight(root.right);

         }

         return n;

     }

这对我来说似乎更合法。会不会是第一个版本失败的情况？

Answer 1

像这样的方法永远不应该使用静态字段，或任何与此相关的字段。right任务是统计正确节点的个数，其实就是统计不为空的节点个数。您实际上并不是在计算节点，而是在计算对节点的引用。这也意味着您必须扫描所有节点，这意味着该方法必须遍历左右。最后，根据定义，根节点不是右节点。public int countRight(NodeT node) {    if (node == null)        return 0;    if (node.right == null)        return countRight(node.left);    return 1 + countRight(node.left) + countRight(node.right);}

Answer 2

你的第一个代码将重新运行 2 不会返回 1 递归调用返回 1+另一个更深层次的调用直到 root.right==null根据您的结构将导致 2 返回您编码的树与您绘制的树不同