给定一个二叉搜索树和一个数字,找到一条路径,该路径的节点数据添加到给定的数字。

发布于 2024-12-23 03:28:31 字数 169 浏览 1 评论 0原文

给定一棵二叉搜索树和一个数字,查找是否存在从根到叶子的路径,使得该路径上的所有数字相加等于给定数字。

我知道如何递归地做到这一点。但是,我更喜欢迭代解决方案。

如果我们每次从根迭代到叶子,就会出现重叠,因为某些路径可能有重叠。

如果树不是二分查找怎么办?

谢谢

Given a binary search tree and a number, find if there is a path from root to a leaf such that all numbers on the path added up to be the given number.

I know how to do it by recursively. But, I prefer an iterative solution.

If we iterate from root to a leaf each time, there will be overlap because some paths may have overlap.

What if the tree is not binary search ?

Thanks

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

娇柔作态 2024-12-30 03:28:31

基本上这个问题可以使用树上的动态编程来解决,以避免那些重叠的路径。

基本思想是跟踪从每个叶子到表 f[node] 中给定节点的可能长度。如果我们用二维布尔数组来实现,它就像f[node][len],表示是否存在从叶子到节点的路径长度等于len。我们还可以使用向量来存储每个f[node]中的值,而不是使用布尔数组。无论您使用哪种表示形式,不同f之间的计算方式都很简单,形式为

f[node] is the union of f[node->left] + len_left[node] and f[node->right] + len_right[node].

二叉树的情况,但将其扩展到非二叉树确实很容易- 树案例。

如果还有什么不清楚的地方,欢迎大家留言评论。

Basically this problem can be solved using Dynamic Programming on tree to avoid those overlapping paths.

The basic idea is to keep track of the possible lengths from each leaf to a given node in a table f[node]. If we implement it in a 2-dimensional boolean array, it is something like f[node][len], which indicates whether there is a path from a leaf to node with length equal to len. We can also use a vector<int> to store the value in each f[node] instead of using a boolean array. No matter what kind of representation you use, the way you calculate between different f are straightforward, in the form of

f[node] is the union of f[node->left] + len_left[node] and f[node->right] + len_right[node].

This is the case of binary tree, but it is really easy to extend it to non-binary-tree cases.

If there is anything unclear, please feel free to comment.

指尖上得阳光 2024-12-30 03:28:31

任何可以递归执行的操作,也可以迭代执行。但是,递归解决方案没有性能问题,那么我将保持原样。如果您尝试迭代地进行编码/阅读,那么编码/阅读很可能会更加困难。

但是,如果您坚持,您可以使用堆栈将递归解决方案转换为迭代解决方案。每次进行递归调用时,将当前函数调用中的状态变量压入堆栈。完成通话后,弹出变量。

Anything you can do recursively, you can also do iteratively. However you are not having performance issues with the recursive solution, then I would leave it as is. It would more likely than not be more difficult to code/read if you try to do it iteratively.

However if you insist, you can transform your recursive solution into an iterative one by using a stack. Every time you make a recursive call, push the state variables in your current function call onto the stack. When you are done with a call, pop off the variables.

黒涩兲箜 2024-12-30 03:28:31

对于 BST:

Node current,final = (initialize)
List nodesInPath;
nodesInPath.add(current);
while(current != final) {
    List childrenNodes = current.children;
    if(noChildren) noSolution;
    if(current < final) {
        //choose right child if there is one, otherwise no solution
        current = children[right];
    } else if(current > final){
        //choose left child if there is one, otherwise no solution
        current = children[left];         
    } 
    nodesInPath.add(current);
}
check sum in the nodesInPath

但是,对于非 BST,如果您不想,您应该按照 derekhh 建议使用动态规划来应用解决方案一遍又一遍地计算相同的路径。我认为,您可以存储某个已处理节点和根节点之间的总长度。当您扩展距离时,您可以计算距离。然后,您将应用广度优先搜索,不再遍历相同的路径并使用之前计算的总距离。我想到的算法有点复杂,抱歉,但没有足够的时间来编写它。

For BST:

Node current,final = (initialize)
List nodesInPath;
nodesInPath.add(current);
while(current != final) {
    List childrenNodes = current.children;
    if(noChildren) noSolution;
    if(current < final) {
        //choose right child if there is one, otherwise no solution
        current = children[right];
    } else if(current > final){
        //choose left child if there is one, otherwise no solution
        current = children[left];         
    } 
    nodesInPath.add(current);
}
check sum in the nodesInPath

However, for non BST you should apply a solution using dynamic programming as derekhh suggests if you don't want to calculate same paths over and over again. I think, you can store the total length between a certain processed node and the root node. You calculate the distances when you expand them. Then you would apply Breadth-first search to not to traverse same paths again and use previously computed total distances. The algorithm comes to my mind is a little complex, sorry but not have enough time to write it.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文