定二叉查找树和一个数，查找其节点的数据添加到被给定数的路径。 [英] Given a binary search tree and a number, find a path whose node's data added to be the given number.

问题描述

给定的二进制搜索树和一个数，发现如果存在来自根的路径的片，使得所述路径上的所有数字加起来为给定数。

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.

我知道如何通过递归地做到这一点。但是，我preFER迭代求解。

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 ?

感谢

推荐答案

基本上，这个问题可以通过在树动态规划，以避免那些重叠的路径来解决。

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

的基本思想是跟踪的可能长度从每个叶给定节点中的表 F [节点] 。如果我们在一个二维布尔数组实现它，这多少有点像 F [节点] [LEN] ，这表明是否有来自叶子的路径节点长度等于 len个。我们也可以使用矢量＆lt; INT＆GT; 用布尔要存储在每个 F [节点] 的值，而不是数组。不管你用什么样的再presentation，你计算之间的不同 F 的方式很简单，在形式

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.

这篇关于定二叉查找树和一个数，查找其节点的数据添加到被给定数的路径。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！