t****3
发帖数: 8 | 1 毕业之后想着回国去玩，拖到最近才开始担忧。背景是cs bs degree，毕业半年了，没
有实习经验，最近面了aws，5轮有两轮问的binary tree return grandparent of leaf
node，我答的是dfs然后到每个path尾如果是leaf就将path倒数第三个（grandparent
）加到result。实在想不到最优解法。
还有一轮让我设计text editor写code出来，我当时懵了。
问简历的时候回答得也不好。
第二天就收到thank you from。。
我知道自己准备得不好，还有class struct的语法没复习，复习得不好临场没自信一紧
张更想不起来。
现在觉得自己实力很差，很想好好重新复习和写些apps什么的，巩固一下基础。
但是现实也是我必须尽快找到工作，需要有份工作收入维持生活的同时拿时间出来复习
学习。很是迷茫。
不知道该如何找工作，是不是应该去找份最容易找到的餐馆工作然后一边打工一边复习
，还是应该全心复习全心投简历。 |
t****3
发帖数: 8 | 2 现在还是想不出怎么回答binary tree grandparent那条问题。。 大神们有给个hint吗 |
e***y
发帖数: 4307 | 3 即使已经毕业，也应该厚着脸皮去参加学校的招聘会，那是你最好的机会 |
z**********3
发帖数: 22 | 4 Node* FindGrandParent(Node *root, Node *target)
{
if (root == NULL || target == NULL)
return NULL;
if (target == root)
return root;
else if (root->left == NULL && root->right == NULL)
return NULL;
Node *left = FindGrandParent(root->left, target);
if (left == target && root->left != target)
return root;
else if (left != NULL)
return left;
Node *right = FindGrandParent(root->right, target);
if (right == target && root->right != target)
return root;
else if (right != NULL)
return right;
return NULL;
}
没有测试过不知道对不对，O(n) time, O(1) space.
我当时面亚麻也被一个老印搞了，麻蛋让我找top n 我说用min heap，他说你为什么不
用max heap？？你懂不懂heap？？我tm也是日了狗了。面试运气也很重要的。祝楼主找
工作顺利！
leaf
grandparent
【在 t****3 的大作中提到】
: 毕业之后想着回国去玩，拖到最近才开始担忧。背景是cs bs degree，毕业半年了，没
: 有实习经验，最近面了aws，5轮有两轮问的binary tree return grandparent of leaf
: node，我答的是dfs然后到每个path尾如果是leaf就将path倒数第三个（grandparent
: ）加到result。实在想不到最优解法。
: 还有一轮让我设计text editor写code出来，我当时懵了。
: 问简历的时候回答得也不好。
: 第二天就收到thank you from。。
: 我知道自己准备得不好，还有class struct的语法没复习，复习得不好临场没自信一紧
: 张更想不起来。
: 现在觉得自己实力很差，很想好好重新复习和写些apps什么的，巩固一下基础。
|
t****3
发帖数: 8 | 5 学校离我家远。。。
【在 e***y 的大作中提到】
: 即使已经毕业，也应该厚着脸皮去参加学校的招聘会，那是你最好的机会
|
t****3
发帖数: 8 | 6 谢谢你。
你的程序我没看得懂。。 可能我没说清，是要求binary tree的所有leaf nodes的
grandparent， 比如给：
1
/ \
2 3
/ \ / \
5 6 7 8
/
9
return [2,1]
【在 z**********3 的大作中提到】
: Node* FindGrandParent(Node *root, Node *target)
: {
: if (root == NULL || target == NULL)
: return NULL;
:
: if (target == root)
: return root;
: else if (root->left == NULL && root->right == NULL)
: return NULL;
:
|
z**********3
发帖数: 22 | 7 那跟这题应该是差不多的 http://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/ 但是需要排除父节点，返回的时候判断一下是否是子节点就可以了，或者pop掉最后一个父节点。感觉楼主的做法也没问题的说。。 可以用个vector来存储结果
【在 t****3 的大作中提到】
: 谢谢你。
: 你的程序我没看得懂。。 可能我没说清，是要求binary tree的所有leaf nodes的
: grandparent， 比如给：
: 1
: / \
: 2 3
: / \ / \
: 5 6 7 8
: /
: 9
|
t****3
发帖数: 8 | 8 是的，我当时的想法也是这样，但有些边界情况没解释清楚，o(︶︿︶)o 唉 谢谢
【在 z**********3 的大作中提到】
: 那跟这题应该是差不多的 http://www.geeksforgeeks.org/print-ancestors-of-a-given-node-in-binary-tree/ 但是需要排除父节点，返回的时候判断一下是否是子节点就可以了，或者pop掉最后一个父节点。感觉楼主的做法也没问题的说。。 可以用个vector来存储结果
|
d**d
发帖数: 389 | 9 vector grandparents(TreeNode* root)
{
set s;
dfs(nullptr, nullptr, root, s);
std::vector res(s.begin(), s.end());
return res;
}
void dfs( TreeNode* g, TreeNode* p, TreeNode* root, set&res)
{
if (root == nullptr) return;
if (root->left == nullptr && root->right == nullptr)
{
if (g) res.insert(g->val);
return;
}
if (root->left)
dfs(p, root, root->left, res);
if (root->right)
dfs(p, root, root->right, res);
}
【在 t****3 的大作中提到】
: 谢谢你。
: 你的程序我没看得懂。。 可能我没说清，是要求binary tree的所有leaf nodes的
: grandparent， 比如给：
: 1
: / \
: 2 3
: / \ / \
: 5 6 7 8
: /
: 9
|
l*****e
发帖数: 101 | 10 哈哈 楼主太可爱了！
【在 t****3 的大作中提到】
: 学校离我家远。。。
|
