由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一道g算法题
相关主题
一道google面试题微软面试的一道题
如何随机找二叉树中的任意节点?讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径
一道在线题G家intern电面新鲜面经
求教Leetcode题目:Lowest Common Ancestor二叉树按层次打印有没有办法换行显示?
回馈本版,新鲜店面,新题新气象Amazon onsite真的只要暴力解就行了么
热腾腾的 LinkedIn 电面题攒RP问tree的iterative traversal
到底什么样的二叉树才是平衡二叉树?leetcode valid bst new test cases 过不去了。。。
一道二叉树的老题python里面怎么表示树?
相关话题的讨论汇总
话题: nodes话题: root话题: treenode话题: int话题: len
进入JobHunting版参与讨论
1 (共1页)
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
5
时间和空间复杂度都是
O(树的大小)。
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 的大作中提到】
: 拓扑排序?
:
: 干净

1 (共1页)
进入JobHunting版参与讨论
相关主题
python里面怎么表示树?回馈本版,新鲜店面,新题新气象
Interview question::热腾腾的 LinkedIn 电面题攒RP
贴个自己的答案:Binary Tree Max Path Sum到底什么样的二叉树才是平衡二叉树?
这最小公共父母节点有bug吗?一道二叉树的老题
一道google面试题微软面试的一道题
如何随机找二叉树中的任意节点?讨论Amazon的一道题:根节点到叶节点之间最小和,并打印路径
一道在线题G家intern电面新鲜面经
求教Leetcode题目:Lowest Common Ancestor二叉树按层次打印有没有办法换行显示?
相关话题的讨论汇总
话题: nodes话题: root话题: treenode话题: int话题: len