p*y
发帖数: 108 | 1 就是一棵树或者森林，让你依次摘掉并打印叶节点；然后循环上述步骤，直到把树消干净
应该怎么个思路？
请大家讨论一下 |
r****7
发帖数: 2282 | 2 怎么个依次法？
我感觉就是后序遍历啊，还是哪儿理解的有偏差？
干净
【在 p*y 的大作中提到】
: 就是一棵树或者森林，让你依次摘掉并打印叶节点；然后循环上述步骤，直到把树消干净
: 应该怎么个思路？
: 请大家讨论一下
|
l*********8
发帖数: 4642 | 3 拓扑排序?
干净
【在 p*y 的大作中提到】
: 就是一棵树或者森林，让你依次摘掉并打印叶节点；然后循环上述步骤，直到把树消干净
: 应该怎么个思路？
: 请大家讨论一下
|
k******4
发帖数: 94 | 4 节点按照他们离最远的在其子树中的叶子节点的距离分配到不同的vector里面，
void push_nodes(unordered_map> &nodes, TreeNode *root
, int len)
{
if (nodes.find(len) == nodes.end())
{
vector temp(1, root);
nodes[len] = temp;
}
else
nodes[len].push_back(root);
return;
}
int printAndDeleteLeavesHelper(TreeNode *root, unordered_map
TreeNode*>> &nodes)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
{
push_nodes(nodes, root, 1);
return 1;
}
int from_left = printAndDeleteLeavesHelper(root->left, nodes);
int from_right = printAndDeleteLeavesHelper(root->right, nodes);
int max_len_from_leaves = max(from_left, from_right);
push_nodes(nodes, root, max_len_from_leaves);
return max_len_from_leaves;
}
void printTree(TreeNode *root)
{
if (root == NULL)
return;
unordered_map(int, vector
printAndDeleteLeavesHelper(nodes, root);
int i=1;
while (nodes.find(i) != nodes.end())
{
for(int j=0; j
print nodes[i][j];
}
return;
} |
k******4
发帖数: 94 | |
s***c
发帖数: 639 | 6 是二叉树么，还是个graph，有环没？
要不就按层打印，倒着打，打印完了就削掉
干净
【在 p*y 的大作中提到】
: 就是一棵树或者森林，让你依次摘掉并打印叶节点；然后循环上述步骤，直到把树消干净
: 应该怎么个思路？
: 请大家讨论一下
|
u****x
发帖数: 97 | 7 问下
是否先打印当前所有叶节点
然后virtually除去这一圈叶节点
以上做为一个iteration
干净
【在 p*y 的大作中提到】
: 就是一棵树或者森林，让你依次摘掉并打印叶节点；然后循环上述步骤，直到把树消干净
: 应该怎么个思路？
: 请大家讨论一下
|
u****x
发帖数: 97 | 8 是指按各节点所在高度打印 是吧
叶节点高度为0
然后打印高度为1的节点
依次类推
root
【在 k******4 的大作中提到】
: 节点按照他们离最远的在其子树中的叶子节点的距离分配到不同的vector里面，
: void push_nodes(unordered_map> &nodes, TreeNode *root
: , int len)
: {
: if (nodes.find(len) == nodes.end())
: {
: vector temp(1, root);
: nodes[len] = temp;
: }
: else
|
k******4
发帖数: 94 | 9 空树对应0，叶子是1，依次类推。
【在 u****x 的大作中提到】
: 是指按各节点所在高度打印 是吧
: 叶节点高度为0
: 然后打印高度为1的节点
: 依次类推
:
: root
|
k******4
发帖数: 94 | 10 我居然惯性得认为是二叉树，这点确实需要等待Lz明确下。
【在 s***c 的大作中提到】
: 是二叉树么，还是个graph，有环没？
: 要不就按层打印，倒着打，打印完了就削掉
:
: 干净
|
k******4
发帖数: 94 | 11 我理解是这个意思，但是需要等lz明确下是否二叉树。
【在 u****x 的大作中提到】
: 问下
: 是否先打印当前所有叶节点
: 然后virtually除去这一圈叶节点
: 以上做为一个iteration
:
: 干净
|
h***k
发帖数: 161 | 12 我觉得如果每次只删除叶节点的话就dfs，因为不一定每次删的leaf在同一个高度：
while(root has children) {
helper(root, root.left);
helper(root, root.right);
}
helper(Node parent, Node child) {
if (child has no children){
parent.left/right = null; // check if its left or right of parent.
} else {
helper(child, child.right);
helper(child, child.left);
}
}
当然复杂度有点高。。 |
a******u
发帖数: 69 | 13 re.
用个Queue来存度数为1的点。
【在 l*********8 的大作中提到】
: 拓扑排序?
:
: 干净
|
