BST节点的列表创建
BST节点的列表创建
提问于 2012-05-28 17:28:30
我希望在每个深度创建二叉树节点的列表。
所以如果深度是X，我就会有X个列表。
请看我的方法。我认为这是正确的。我相信这是正确的吗？欢迎任何投入：
public List<List<BinaryNode>> getNodesPerDepth(BinaryNode root){
if(root == null) {
throw new IllegalArgumentException();
}
List<LinkedList<BinaryNode>> result = new LinkedList<LinkedList<BinaryNode>>();
result.add(new LinkedList<BinaryNode>());
getNodesPerDepth(result, root, 0);
return result;
}
private void getNodesPerDepth(List<LinkedList<BinaryNode>> lists, BinaryNode root , int depth){
if(root == null){
return;
}
lists.get(depth).add(root);
if(lists.size() < depth + 1 && (root.left != null || root.right != null)){
lists.add(new LinkedList<BinaryNode>());
}
getNodesPerDepth(lists, root.left, depth + 1);
getNodesPerDepth(lists, root.right, depth + 1);
} 回答 1
Code Review用户
回答已采纳
发布于 2012-05-29 05:36:34
您真的想在这个问题上进行递归吗？最坏情况下的二叉树可能是线性列表。一个更好的办法是做一些这样的事情：
getNodesPerDepth(rootNode) {
list.add(rootNode); // Start with the root node,
dlst = new List() // depth lit
while(list.size() != 0) {
nextlst = new List(); // make a list of children to iterate next phase.
for(e : list) {
for (c : e.children())
nextlst.add(c);
}
dlst.add(list);
list = nextlst;
}
return dlst;
}页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/12127
复制相关文章
相似问题
腾讯云开发者
