l***i
发帖数: 1309 | 1 Your function should return a vector or you need to restore path[]
before making the call to right subtree |
|
s******n
发帖数: 3946 | 2 int sum = 0;
queue.add(root)
while (queue.size < K) {
node = queue.pop()
sum += node.value
queue.add(node.children)
}
create "queue.size" threads to sum each subtree
wait threads to finish....
for (int i=0; i
P.S.没看见要求每个node都要标sum，这样的话最后一步复杂点 |
|
s******n
发帖数: 3946 | 3 int sum = 0;
queue.add(root)
while (queue.size < K) {
node = queue.pop()
sum += node.value
queue.add(node.children)
}
create "queue.size" threads to sum each subtree
wait threads to finish....
for (int i=0; i
P.S.没看见要求每个node都要标sum，这样的话最后一步复杂点 |
|
m*****y
发帖数: 93 | 4 1. Compute the depth of its subtree on each node, using a recursive way.
2. For any node u, the length of longest path "turning at this node" is
depth(u->left) + depth(u->right) + 2. Therefore, for each node u, compute
the length and take the maximum one.
Both steps are O(n). |
|
m*****y
发帖数: 93 | 5 1. Compute the depth of its subtree on each node, using a recursive way.
2. For any node u, the length of longest path "turning at this node" is
depth(u->left) + depth(u->right) + 2. Therefore, for each node u, compute
the length and take the maximum one.
Both steps are O(n). |
|
w**z
发帖数: 8232 | 6 错了。你最后一个return hit 不到了 if left subtree is not empty. complain 一下也没什么。人之常情嘛。但该做题还得做，别耽误了。道理大家都懂的 |
|
|
G**********s
发帖数: 70 | 8 最近系统做了BT/BST的题目，做过的最难的是 largest BST (木有subtree) in BT，那
个recursion真的很tricky，说到这道题，我想问一下，bottom-up来解这道题是不是就
是DP的应用，对应的top-down就是DC，对吧？看来是时候系统做DP/DC题目了。。。 |
|
|
v****c
发帖数: 29 | 10 int f(const std::string& str, int start, int& end)
{
if(start < str.size() && str[start] == '0')
{
end = start;
return 0;
}
else if(start < str.size() && str[start] == '(')
{
int t; // position of last letter in the left subtree
int left = f(str, start + 1, t);
if(left == -1) return -1;
int right = f(str, t + 1, end);
if(right == -1 || ++end == str.size() || str[end] != ')') return -1;
return std::max(left, right... 阅读全帖 |
|
H****r
发帖数: 2801 | 11 Unless the LCA for nodes that's processed has memory otherwise it's still
gona be processed it seems...
// code from the article: ///
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in L&
R subtrees
} |
|
s******o
发帖数: 2233 | 12 第四版的4.8：
You are given a binary tree in which each node contains a value. Design an
algorithm to print all paths which sum up to that value. Note that it can be
any path in the tree - it does not have to start at the root.
书上的解法貌似只考虑root左边或者右边subtree里的path，比如下面这个找sum=6的就
找不出来，
2
1 3
想确认一下我的理解对不对。如果需要考虑这种情况有什么简洁点的做法？ |
|
t********3
发帖数: 567 | 13 if this node has right subtree, get the min node from that.
if not, travel from root node to current node, store the path in some kind
of list/or stack etc. iterate back according to the list/stack, the
successor is the first right parent node |
|
x*******6
发帖数: 262 | 14 对B建一个suffixtree，然后从里面找出路径为字符串A的internal node，数数这个
node
的subtree有几个leaf。线性复杂度 |
|
l***i
发帖数: 1309 | 15 Do you really need two sequences, seems one of them suffices since you have
is_leaf information. Let's look at preorder sequence:
let the sequence be node[0] to node[n-1]
you know node[n-1] has to be a leaf, actually the last leaf if you order the
leaves left to right.
Now start from pos=n-1, pos-- until you hit a node[i] which is_leaft ==
false. This node has to be the parent of node[i+1..n-1]. So you construct
such a tree node with the children i+1 to n-1. Now you can treat the tree
node as a ... 阅读全帖 |
|
b*****s
发帖数: 36 | 16 我这里树上标的数字没有实际意义。
我的意思是，这个tree符合（2）的定义却不符合（1）的定义。（2）允许不同subtree
的leaf之间height之差大于1，而（1）不允许。 |
|
|
p**l
发帖数: 125 | 18 可能我没怎么懂你的意思, 如果你想的是以n1为root来做subtree做bfs, 那就误会我的
意思了.
至于child 1 和 child 2 和child n是否是因为兄弟而related. 我不认为这样的假设
有道理. 因为如果是的话, 那同父异母也可以? 当然如果是看blood构成成分的话这就
完全是另一道题了, 比如1/32的father blood和1/64father blood也可能是related.
但这样的不确定性不会用来出题的. 我还是觉得这是一个tree/hashtable的题. |
|
p**l
发帖数: 125 | 19 可能我没怎么懂你的意思, 如果你想的是以n1为root来做subtree做bfs, 那就误会我的
意思了.
至于child 1 和 child 2 和child n是否是因为兄弟而related. 我不认为这样的假设
有道理. 因为如果是的话, 那同父异母也可以? 当然如果是看blood构成成分的话这就
完全是另一道题了, 比如1/32的father blood和1/64father blood也可能是related.
但这样的不确定性不会用来出题的. 我还是觉得这是一个tree/hashtable的题. |
|
f****e
发帖数: 34 | 20 你的标题中BST有误... 这题是G家面我的题....
用f[i]表示根节点为i的子树种的max path sum.
那么
f[i]=max(f[left[i]], f[right[i]], g[left[i]]+g[right[i]]+w[i])
其中w[i]表示i节点的权重，g[x]表示从节点x，只能往下走，能够走出的最大的path
sum.
代码也很好些
int solve(TreeNode *root, int &g) {
if (!root) {
g = 0;
return 0;
}
int f = 0;
int leftG = 0, rightG = 0;
if (root->left) f = max(f, solve(root->left, leftG));
if (root->right) f = max(f, solve(root->right, rightG);
f = max(f, leftG + rightG + root->val);
g = root->val +... 阅读全帖 |
|
l*********8
发帖数: 4642 | 21 binary tree 还是BST?
每个node上的值一定是正数吗？
root
subtree |
|
m*****k
发帖数: 731 | 22 seems a tree version of SubArrayLargestSum problem.
root
subtree |
|
l*****i
发帖数: 136 | 23 这道题是问max path， 还是max subtree？
用简单的case test
4
/ \
5 6
如果是max path, 我感觉应该返回 10，你的代码返回的是15 |
|
|
f*****e
发帖数: 2992 | 25 每个节点向父节点，传(min,max) of subtree? |
|
w****x
发帖数: 2483 | 26 代码写成这样就挂了，我记得写的大概只有这得一半 |
|
d******i
发帖数: 76 | 27
想了想，不知道怎么写的更加简洁，能否给点意见，谢谢了 |
|
p*****2
发帖数: 21240 | 28
int ans=0;
boolean dfs(Node root)
{
if(root==null)
return true;
boolean l=dfs(root.left);
boolean r=dfs(root.right);
if(l && r && (root.left==null || root.left.val==root.val) && (root.
right==null || root.right.val==root.val))
{
ans++;
return true;
}
return false;
} |
|
|
|
|
|
|
l*********8
发帖数: 4642 | 34 刚写了一个，发现跟二爷的很像啊，呵呵。
inline bool diffVar(Node* p, Node* q) { return p&&q && p->var != q->var;};
bool uniVar(Node * root, int & num)
{
if (!root)
return true;
if ( uniVar(root->left, num) && !diffVar(root, root->left)
&& uniVar(root->right,num) && !diffVar(root, root->right)) {
num++;
return true;
}
return false;
} |
|
|
|
|
l*********8
发帖数: 4642 | 38 恩， 我一开始就写错了。 错误代码如下：
inline bool diffVar(Node * p, Node* q) { return p&&q && p->var != q->var;};
bool uniVar(Node * root, int & num)
{
if (!root)
return true;
if ( !uniVar(root->left, num) || diffVar(root, root->left)
|| !uniVar(root->right,num) || diffVar(root, root->right)) {
return false;
}
num++;
return true;
} |
|
|
p*****2
发帖数: 21240 | 40
uniVar(root->left, num) && !diffVar(root, root->left)
&& uniVar(root->right,num) && !diffVar(root, root->right)
这句，如果uniVar returns false。会不会有问题？ |
|
l*********8
发帖数: 4642 | 41 说的对！ 还是我之前错误代码犯得错误！ 在同一个地方摔倒了两次啊。。。 |
|
l*********8
发帖数: 4642 | 42 呵呵，再改就更和二爷的一样了。 要把递归提出去保证执行。 |
|
p*****2
发帖数: 21240 | 43
其实我也犯了这个错误了。我测试结果不对，呵呵。所以我说这题一遍能写对真的是大
牛了。 |
|
|
c*****a
发帖数: 808 | 45 不知道行不行，只测试了几个case
public static int findUni(BSTNode node){
if(node == null) return 0;
if((node.left==null || node.left.data == node.data) &&
(node.right==null ||node.right.data == node.data))
return findUni(node.left) + findUni(node.right) + 1;
else return findUni(node.left) +findUni(node.right);
} |
|
l*********8
发帖数: 4642 | 46 反例
2
\
2
\
3
答案是0， 你返回1 |
|
c*****a
发帖数: 808 | 47
不知道是不是我理解错了。这个树里面，那个3是不是?我看题目里面的例子每个child
都算1个 |
|
l*********8
发帖数: 4642 | 48 不好意思，我说错了。答案应该是1.
你测试这个case的结果是多少？
child |
|
c*****a
发帖数: 808 | 49 看了上面的code， 我的code应该错了，我的只检查每2个level
2
2 2
2 2
2 2
1 1
应该会出错 |
|
m**********0
发帖数: 356 | 50 可不可以解释一下，我怎么看不出来问题呢(godlike的code)？谢谢！ |
|
