如何獲取樹的所有葉節點？

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; 
}