l*********y
发帖数: 370 | 1 Given a binary tree, find the minimum sum from root to the leaf and also print that path? |
S*******w
发帖数: 24236 | 2 dp?
the
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
|
a********m
发帖数: 15480 | |
a********m
发帖数: 15480 | 4 感觉dp似乎木有啥帮助。本来也是要遍历。
【在 S*******w 的大作中提到】
: dp?
:
: the
|
S*******w
发帖数: 24236 | 5 shortest path algorithm都行啊
【在 S*******w 的大作中提到】
: dp?
:
: the
|
S*******w
发帖数: 24236 | 6 dp可以解。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
|
q****x
发帖数: 7404 | 7 有帮助。省下重复计算。
【在 a********m 的大作中提到】
: 感觉dp似乎木有啥帮助。本来也是要遍历。
|
a********m
发帖数: 15480 | 8 不管是遍历还是dij所有新节点的值都是没有计算过的。没有重复计算吧。
【在 q****x 的大作中提到】
: 有帮助。省下重复计算。
|
l*********y
发帖数: 370 | 9 难点在如何打印最短路径。dp的话得先遍历一遍才能得到有多少个节点吧。 |
l*********y
发帖数: 370 | 10 Dij的话不是weight在边上,这个是weight在节点上。 |
|
|
a********m
发帖数: 15480 | 11 这个无所谓。你可以把节点上的值当成it到父节点的路径weight。root的反正要加在所
有路径上，没关系了。
【在 l*********y 的大作中提到】
: Dij的话不是weight在边上,这个是weight在节点上。
|
q****x
发帖数: 7404 | 12 那不就是dp。
【在 a********m 的大作中提到】
: 不管是遍历还是dij所有新节点的值都是没有计算过的。没有重复计算吧。
|
D********g
发帖数: 650 | 13 如果可以自定义tree node structure应该很容易，每个节点上加一个sumFromRoot和
parent指针就可以了。
print that path?
【在 l*********y 的大作中提到】
: Given a binary tree, find the minimum sum from root to the leaf and also print that path?
|
a********m
发帖数: 15480 | 14 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
理解， 哪个大牛来说一说？
【在 q****x 的大作中提到】
: 那不就是dp。
|
q****x
发帖数: 7404 | 15 通过记录之前的结果避免重复计算。
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
|
y**********u
发帖数: 6366 | 16 这题和dp有什么关系啊
就是dfs，每次找到的路径sum可以作为约束，用来剪枝
站: BBS 未名空间站 (Sun Jan 1 22:36:30 2012, 美东)
【在 S*******w 的大作中提到】
: dp可以解。
|
y**********u
发帖数: 6366 | 17 不需要
维护2个stack，每次Pop的时候，第一个stack得到访问的节点，第二个stack是根到该
节点的sum
【在 a********m 的大作中提到】
: 。。。。。。dp本质是避免重复计算呀。。。。木有重复计算咋算dp? 这个是俺自己的
: 理解， 哪个大牛来说一说？
|
H***e
发帖数: 476 | 18 这题跟dp啥关系啊？
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
currentSum = currentSum + node.key;
path.add(node);
if (node.left == null && node.right == null) {
if (currentSum < minSum) {
minSum = currentSum;
minPath.clear();
minPath.addAll(path);
}
return;
}
minSumPathFromRootToLeave(node.left, path, currentSum);
minSumPathFromRootToLeave(node.right, path, currentSum);
path.remove(node);
}
public void printMinSumPathFromRootToLeave() {
ArrayList path = new ArrayList();
int currentSum = 0;
minSumPathFromRootToLeave(root, path, currentSum);
for (BSTNode node : minPath) {
System.out.print(node.key + " ");
}
} |
a********m
发帖数: 15480 | 19 恩。dij还要排序，不值得。直接遍历就好了。
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List minPath = new ArrayList();
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList path, int currentSum) {
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
|
p*****2
发帖数: 21240 | 20 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
static void minSum(Node root)
{
if (root == null)
return;
List list = new List();
List minlist = new List();
list.Add(root);
Check(list, ref minlist);
Console.WriteLine(minlist.Count-1);
foreach (Node i in minlist)
i.Print();
}
static void Check(List list, ref List minlist)
{
Node node = list[list.Count - 1];
if (node.left == null && node.right==null)
{
if (minlist.Count==0 || minlist.Count>list.Count)
{
minlist.Clear();
minlist.AddRange(list);
}
}
else
{
if (node.left != null)
{
list.Add(node.left);
Check(list, ref minlist);
}
if (node.right != null)
{
list.Add(node.right);
Check(list, ref minlist);
}
}
list.RemoveAt(list.Count - 1);
} |
|
|
f*******l
发帖数: 66 | 21 C++ version
class Node
{
public:
Node() {
leftChild = NULL ;
rightChild = NULL ;
}
~Node() {}
int value ;
Node *leftChild ;
Node *rightChild ;
};
// pre-order traverse
void traverseTree(Node *treeNode, vector &path , vector
*> &miniPath, int &minSum, int ¤tSum)
{
if ( treeNode!=NULL )
{
currentSum += treeNode->value ;
}
else
{
if( currentSum < minSum )
{
minSum = currentSum ;
miniPath.clear() ;
for (int i = 0 ; i < path.size() ; i++)
{
miniPath.push_back( path[i] );
}
}
return ;
}
if ( currentSum > minSum )
{
return ;
}
path.push_back(treeNode) ;
traverseTree(treeNode->leftChild, path, miniPath, minSum, currentSum) ;
traverseTree(treeNode->rightChild, path, miniPath, minSum, currentSum) ;
path.pop_back();
currentSum -= treeNode->value ;
return ;
}
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
|
m***n
发帖数: 2154 | 22 public int miniSum(Node tree) {
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) return tree.
value;
int left= miniSum(tree.left);
int right = miniSum(tree.right);
return Math.min(left,right)+tree.value;
} |
m***n
发帖数: 2154 | 23 带返回路径的
public int miniSum(Node tree, ArrayList pre) {
if(tree==null) return 0;
if(tree!=null && tree.left ==null && tree.right==null) {
pre.add(tree);
return tree.value;
}
ArrayList storeresult = new ArrayList();
int left= miniSum(tree.left, storeresult);
ArrayList storeresultright = new ArrayList();
int right = miniSum(tree.right,storeresultright);
pre.add(tree);
if(left
pre.addAll(storeresult);
}
else{
pre.addAll(storeresultright);
}
return Math.min(left,right)+tree.value;
} |
h********w
发帖数: 221 | 24 mark一下，顺便support这个解法
【在 H***e 的大作中提到】
: 这题跟dp啥关系啊？
: 也用不着dijkstra,就是简单的pre-order traversal就可以勒。
: inside a class:
: private List minPath = new ArrayList();
: private int minSum = Integer.MAX_VALUE;
: private void minSumPathFromRootToLeave(BSTNode node,
: ArrayList path, int currentSum) {
: //path is the path from root to node's parent,
: //currentSum is sum from root till node's parent
: // add base cases here:
|
z******w
发帖数: 36 | |
e***s
发帖数: 799 | 26 请教大牛,
List 不是应该 pass by reference implicity吗?为什么要ref 在前面?
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
|
e***s
发帖数: 799 | 27 我编译跑了一遍，不对啊。。。。。。
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
|
e***s
发帖数: 799 | 28 要改这一句才对吧
minlist.Sum(n => n.Value) > list.Sum(n => n.Value)
【在 p*****2 的大作中提到】
: 我写了个C#的，发现在纸上写好，到了VS上还是要改很多。
: static void minSum(Node root)
: {
: if (root == null)
: return;
: List list = new List();
: List minlist = new List();
: list.Add(root);
: Check(list, ref minlist);
: Console.WriteLine(minlist.Count-1);
|
