java - 在不使用 if 条件的情况下计算二叉树中的叶子

Question

我知道有一种通用算法可以通过检查节点是否没有左右子节点来递归地计算叶子的数量。但是我想使用多态代码编写相同的代码并检查它是否可能，现在我被困在检查叶子条件但该信息并不完全依赖于当前节点，下面是我到目前为止实现的代码:

import java.util.*;
import java.lang.*;
import java.io.*;


abstract class Tree {
  abstract int count();
}

class Empty extends Tree {
  public int count() {
    return 0;   
  }
}

class NonEmpty extends Tree {

  private final int val;
  private final Tree left;
  private final Tree right;

  public NonEmpty(int val, Tree left, Tree right) {
    this.val   = val;
    this.left  = left;
    this.right = right;
  }

  public int count() {
    return left.count() + right.count();
  }
}

public class Main {
  public static void main(String[] args) throws java.lang.Exception {
    Tree t = new NonEmpty(5, new Empty(), new Empty());
    System.out.println(t.count()); // 0 but should be 1
  }
}

更新 1

我和我的几个同事讨论过这个想法，我受到了很多批评，所以这是一个坏主意吗？我的观点是对我来说感觉很干净，我想听听其他人的意见。

Answer 1

最终解决方案:

interface Tree {
    Tree NULL_TREE = new NullTree();

    int countLeafs();
    Tree left();
    Tree right();
}

class NullTree implements Tree {
    @Override
    public int countLeafs() {
        return 0;
    }

    @Override
    public Tree left() {
        return this;
    }

    @Override
    public Tree right() {
        return this;
    }
}

class Leaf implements Tree {
    private int val;

    public Leaf(int val) {
        this.val = val;
    }

    public int countLeafs() {
        return 1;
    }

    @Override
    public Tree left() {
        return NULL_TREE;
    }

    @Override
    public Tree right() {
        return NULL_TREE;
    }
}

class Node implements Tree {

    private final int val;
    private final Tree left;
    private final Tree right;

    public Node(int val, Tree left, Tree right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public int countLeafs() {
        return left.countLeafs() + right.countLeafs();
    }

    @Override
    public Tree left() {
        return left;
    }

    @Override
    public Tree right() {
        return right;
    }
}

public class Main {
    public static void main(String[] args) throws java.lang.Exception {
        Tree t = new Node(5, new Leaf(10), new Leaf(20));
        System.out.println(t.countLeafs());
    }
}