java 如何获取树的所有叶节点？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31384894/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-11-02 18:31:10 来源:igfitidea点击:
How to get all leaf nodes of a tree?
提问by Frank
Suppose I have a node in a tree, how can I get all leaf nodes whose ancestor is this node? I have defined the TreeNode like this:
假设我在树中有一个节点，如何获取其祖先是该节点的所有叶节点？我已经像这样定义了 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;
}
}
回答by tobias_k
Use recursion.
使用递归。
- if the node itself is a leaf, return it
- otherwise, return all the leaf-nodes of its children
- 如果节点本身是叶子，则返回它
- 否则，返回其子节点的所有叶节点
Something like this (not tested):
像这样（未测试）：
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;
}
回答by thenish
Create a stack and push root node.
创建堆栈并推送根节点。
Stack<Node> st = new Stack<>();
st.push(root);
CL(st.peek());
Call the recursive method.
调用递归方法。
public void CL(Node root){
if (st.peek().left == null && st.peek().right == null ) {//if leaf node
System.out.println(st.peek().data);//print
st.pop();
return;
}
else{
if(st.peek().left != null){
st.add(st.peek().left);
CL(st.peek());
}
if(st.peek().right != null){
st.add(st.peek().right);
CL(st.peek());
}
}
st.pop();
}
