如何获取树的所有叶节点？

Question

假设我在树中有一个节点，我怎样才能得到其祖先是这个节点的所有叶节点？我已经定义了TreeNode，像这样：

public class TreeNode<T> 
{ 
    /** all children of the node */ 
    private List<TreeNode<T>> children = new ArrayList<TreeNode<T>>(); 
    /** the parent of the node, if the node is root, parent = null */ 
    private TreeNode<T> parent = null; 
    /** the stored data of the node */ 
    private T data = null; 

    /** the method I want to implement */ 
    public Set<TreeNode<T>> getAllLeafNodes() 
    { 
     Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>(); 
     return leafNodes; 
    } 
} 

Answer 1

使用递归。

• 如果节点本身是叶，返回它
• 否则，返回其子项的所有叶子节点

像这样（未测试）：

public Set<TreeNode<T>> getAllLeafNodes() { 
    Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>(); 
    if (this.children.isEmpty()) { 
     leafNodes.add(this); 
    } else { 
     for (TreeNode<T> child : this.children) { 
      leafNodes.addAll(child.getAllLeafNodes()); 
     } 
    } 
    return leafNodes; 
}