计算二叉树的右节点

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 返回您编码的树与您绘制的树不同