Uber onsite

dumpling_suanca 发表于 2015-12-7 04:54
这样是不对的，不能只保留隔层，因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive，就是 ...

你的思路是对的  然后可以用dp优化 这个应该是followup会问吧

你给我发的站内信我等级太低回复不了啊。。。站内发个微信号呗

dumpling_suanca 发表于 2015-12-7 04:54
这样是不对的，不能只保留隔层，因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive，就是 ...

我觉得对于每一个node有val和sum，sum就是最后要求的值
leaf node的话就是node.sum = node.val，之后的话就是root.sum = max(root.left.sum+root.right.sum, (root.left.sum-root.left.val)+(root.right.sum-root.right.val)+root.val)

wtcupup 发表于 2015-12-5 05:50
求第三题的的做法

binary tree inorder traversal + house robber ?

请问uber eat是什么意思，可以详细说说吗？

dumpling_suanca 发表于 2015-12-7 04:54
这样是不对的，不能只保留隔层，因为相邻两个子树的处理方法可能不一样。我的第一反应是recursive，就是 ...

聪明，你说的是对的。楼下提到dp，也是自然而然的。代码就不必要写了，很简单。

tiantiana 发表于 2015-12-5 23:58
Question 3:

need to return all the nodes? Or, only the sum is fine.

同问，请问是返回sum就行了么？

uber eat是什么意思？是送外卖的uber？

starcroce 发表于 2015-12-12 07:43
我觉得对于每一个node有val和sum，sum就是最后要求的值
leaf node的话就是node.sum = node.val，之后的 ...

你这个公式好像有问题，root.sum是以当前node为树的max sum, 也就是说root.sum可能包含root.val也有可能不包含。但是你用root->left->sum - root->left->val + root->right->sum - root->right->val， 你默认了root->left->sum包含root->left->val  ?

请问DP怎么做？这里DP的好处是什么？我用recursive做，每个节点也只计算了一次，因为这里recursive实际上是buttom up计算max sum的值。