Làm thế nào để có được tất cả các nút lá của cây?

Question

Giả sử tôi có một nút trong cây, làm thế nào tôi có thể nhận được tất cả các nút lá có tổ tiên là nút này? Tôi đã xác định TreeNode như sau:

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

Sử dụng đệ quy.

• nếu nút chính nó là một chiếc lá, trả lại
• khác, trả lại tất cả những lá nút con của nó

Something như thế này (không kiểm tra):

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