找到一个目标值的二进制搜索树求和路径

本文介绍了找到一个目标值的二进制搜索树求和路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定的二进制搜索树和目标值，发现所有的路径（如果存在多于一个），其总和达到目标值。它可以是树中的任何路径。它并不必须是从根

例如，在下面的二进制搜索树

2  / \ 1 3

时的总和应该是6，路径 1 - ＆GT; 2 - ＆GT; 3 应印。

解决方案

遍历从根的树，做所有的路径和的后序聚会。使用哈希表来存储一个植根于一个节点下去，只可能的路径。我们可以构造经历一个节点的所有路径，从自身和儿童的路径。

下面是psuedo- code表示实现上述，但只存储的数额，而不是实际的路径。对于自己的路径，你需要存储的终端节点的哈希表（我们知道它在哪里开始，并有在树上两个节点之间只有一条路径）。

函数findsum（树，目标）   ＃遍历孩子   如果树形＆GT;左     findsum（tree.left，目标）   如果树形＆GT;右     findsum（tree.right，目标）   ＃单节点形成一个有效的路径   tree.sums = {tree.value}   ＃添加此节点儿童总和   如果tree.left     对于left_sum在tree.left.sums       tree.sums.add（left_sum + tree.value）   如果tree.right     对于right_sum在tree.right.sums       tree.sums.add（right_sum + tree.value）   ＃难道我们形成的总和？   如果目标tree.sums     我们有一个路径   ＃我们能形成的总和经过该节点和两个孩子？   如果tree.left和tree.right     对于left_sum在tree.left.sums       如果目标 - left_sum在tree.right.sums         我们有一个路径   ＃我们不再需要孩子款项，自由他们的记忆   如果tree.left     删除tree.left.sums   如果tree.right     删除tree.right.sums

此不使用的事实，即树是一个搜索树，所以它可以应用到任何二叉树

有关大树下，哈希表的规模将增长失控。如果只有正值，也可能是更有效地使用由总和索引的数组

Given a binary search tree and a target value, find all the paths (if there exists more than one) which sum up to the target value. It can be any path in the tree. It doesn't have to be from the root.

For example, in the following binary search tree:

2 / \ 1 3

when the sum should be 6, the path 1 -> 2 -> 3 should be printed.

解决方案

Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable to store the possible paths rooted at a node and going down-only. We can construct all paths going through a node from itself and its childrens' paths.

Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).

function findsum(tree, target) # Traverse the children if tree->left findsum(tree.left, target) if tree->right findsum(tree.right, target) # Single node forms a valid path tree.sums = {tree.value} # Add this node to sums of children if tree.left for left_sum in tree.left.sums tree.sums.add(left_sum + tree.value) if tree.right for right_sum in tree.right.sums tree.sums.add(right_sum + tree.value) # Have we formed the sum? if target in tree.sums we have a path # Can we form the sum going through this node and both children? if tree.left and tree.right for left_sum in tree.left.sums if target - left_sum in tree.right.sums we have a path # We no longer need children sums, free their memory if tree.left delete tree.left.sums if tree.right delete tree.right.sums

This doesn't use the fact that the tree is a search tree, so it can be applied to any binary tree.

For large trees, the size of the hashtable will grow out of hand. If there are only positive values, it could be more efficient to use an array indexed by the sum.