以下为面试题。
给你一棵二叉树（不一定是 BST），其中每个节点都包含一个值。设计一种算法来打印总和为该值的所有路径。请注意，它可以是树中的任何路径 - 它不必从根开始。
尽管我能够找到树中所有从根开始的路径都具有给定的总和，但对于不是从根开始的路径，我无法做到这一点。
问问题
31449 次
18 回答
15
嗯，这是一棵树，而不是图表。因此，您可以执行以下操作：
伪代码：
global ResultList
function ProcessNode(CurrentNode, CurrentSum)
CurrentSum+=CurrentNode->Value
if (CurrentSum==SumYouAreLookingFor) AddNodeTo ResultList
for all Children of CurrentNode
ProcessNode(Child,CurrentSum)
好吧，这为您提供了从根开始的路径。但是，您可以进行微小的更改：
for all Children of CurrentNode
ProcessNode(Child,CurrentSum)
ProcessNode(Child,0)
您可能需要考虑一下（我正忙于其他事情），但这基本上应该运行以树中每个节点为根的相同算法
编辑：这实际上只给出了“结束节点”。但是，由于这是一棵树，您可以从这些末端节点开始，然后往回走，直到获得所需的总和。
编辑 2：当然，如果所有值都是正数，那么如果当前总和 >= 所需的总和，则可以中止下降
于 2012-07-04T11:51:12.563 回答
10
这是一个O(n + numResults)答案（与@Somebody 的答案基本相同，但所有问题都已解决）：
- 对二叉树进行前序、中序或后序遍历。
- 在进行遍历时，保持从根节点到当前节点上方节点的节点值的累积和。我们称这个值
cumulativeSumBeforeNode。 - 当您访问遍历中的节点时，将其添加到 key 处的哈希表
cumulativeSumBeforeNode（该 key 处的值将是节点列表）。 - 计算
cumulativeSumBeforeNode与目标总和之间的差值。在哈希表中查找这种差异。 - 如果哈希表查找成功，它应该产生一个节点列表。这些节点中的每一个都代表解决方案的起始节点。当前节点代表每个相应起始节点的结束节点。将每个 [start node, end node] 组合添加到您的答案列表中。如果哈希表查找失败，什么也不做。
- 当您在遍历中完成访问一个节点时，从存储在
cumulativeSumBeforeNode哈希表中 key 的列表中删除该节点。
代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class BinaryTreePathsWithSum {
public static void main(String[] args) {
BinaryTreeNode a = new BinaryTreeNode(5);
BinaryTreeNode b = new BinaryTreeNode(16);
BinaryTreeNode c = new BinaryTreeNode(16);
BinaryTreeNode d = new BinaryTreeNode(4);
BinaryTreeNode e = new BinaryTreeNode(19);
BinaryTreeNode f = new BinaryTreeNode(2);
BinaryTreeNode g = new BinaryTreeNode(15);
BinaryTreeNode h = new BinaryTreeNode(91);
BinaryTreeNode i = new BinaryTreeNode(8);
BinaryTreeNode root = a;
a.left = b;
a.right = c;
b.right = e;
c.right = d;
e.left = f;
f.left = g;
f.right = h;
h.right = i;
/*
5
/ \
16 16
\ \
19 4
/
2
/ \
15 91
\
8
*/
List<BinaryTreePath> pathsWithSum = getBinaryTreePathsWithSum(root, 112); // 19 => 2 => 91
System.out.println(Arrays.toString(pathsWithSum.toArray()));
}
public static List<BinaryTreePath> getBinaryTreePathsWithSum(BinaryTreeNode root, int sum) {
if (root == null) {
throw new IllegalArgumentException("Must pass non-null binary tree!");
}
List<BinaryTreePath> paths = new ArrayList<BinaryTreePath>();
Map<Integer, List<BinaryTreeNode>> cumulativeSumMap = new HashMap<Integer, List<BinaryTreeNode>>();
populateBinaryTreePathsWithSum(root, 0, cumulativeSumMap, sum, paths);
return paths;
}
private static void populateBinaryTreePathsWithSum(BinaryTreeNode node, int cumulativeSumBeforeNode, Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int targetSum, List<BinaryTreePath> paths) {
if (node == null) {
return;
}
addToMap(cumulativeSumMap, cumulativeSumBeforeNode, node);
int cumulativeSumIncludingNode = cumulativeSumBeforeNode + node.value;
int sumToFind = cumulativeSumIncludingNode - targetSum;
if (cumulativeSumMap.containsKey(sumToFind)) {
List<BinaryTreeNode> candidatePathStartNodes = cumulativeSumMap.get(sumToFind);
for (BinaryTreeNode pathStartNode : candidatePathStartNodes) {
paths.add(new BinaryTreePath(pathStartNode, node));
}
}
populateBinaryTreePathsWithSum(node.left, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);
populateBinaryTreePathsWithSum(node.right, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);
removeFromMap(cumulativeSumMap, cumulativeSumBeforeNode);
}
private static void addToMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode, BinaryTreeNode node) {
if (cumulativeSumMap.containsKey(cumulativeSumBeforeNode)) {
List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
nodes.add(node);
} else {
List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>();
nodes.add(node);
cumulativeSumMap.put(cumulativeSumBeforeNode, nodes);
}
}
private static void removeFromMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode) {
List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
nodes.remove(nodes.size() - 1);
}
private static class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
public String toString() {
return this.value + "";
}
public int hashCode() {
return Integer.valueOf(this.value).hashCode();
}
public boolean equals(Object other) {
return this == other;
}
}
private static class BinaryTreePath {
public BinaryTreeNode start;
public BinaryTreeNode end;
public BinaryTreePath(BinaryTreeNode start, BinaryTreeNode end) {
this.start = start;
this.end = end;
}
public String toString() {
return this.start + " to " + this.end;
}
}
}
于 2015-06-17T15:48:48.873 回答
9
根据上面克里斯蒂安的回答：
public void printSums(Node n, int sum, int currentSum, String buffer) {
if (n == null) {
return;
}
int newSum = currentSum + n.val;
String newBuffer = buffer + " " + n.val;
if (newSum == sum) {
System.out.println(newBuffer);
}
printSums(n.left, sum, newSum, newBuffer);
printSums(n.right, sum, newSum, newBuffer);
printSums(n.left, sum, 0, "");
printSums(n.right, sum, 0, "");
}
printSums(root, targetSum, 0, "");
于 2013-11-03T15:56:18.697 回答
3
这是一种nlogn复杂的方法。
- 以中序遍历树。
- 同时维护所有节点以及 a 中的累积和
Hashmap<CumulativeSum, reference to the corresponding node>。 - 现在在给定节点计算从根到节点的累积和，直到节点说这是
SUM。 - 现在
SUM-K在HashMap. - 如果条目存在，则在
HashMap. - 现在我们有了从节点引用到当前节点的有效路径。
于 2013-09-16T12:28:39.327 回答
3
一个干净的 JAVA 解决方案。使用内部递归调用跟踪遍历的路径。
private static void pathSunInternal(TreeNode root, int sum, List<List<Integer>> result, List<Integer> path){
if(root == null)
return;
path.add(root.val);
if(sum == root.val && root.left == null && root.right == null){
result.add(path);
}
else if(sum != root.val && root.left == null && root.right == null)
return;
else{
List<Integer> leftPath = new ArrayList<>(path);
List<Integer> rightPath = new ArrayList<>(path);
pathSunInternal(root.left, sum - root.val, result, leftPath);
pathSunInternal(root.right, sum - root.val, result, rightPath);
}
}
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
pathSunInternal(root, sum, result, path);
return result;
}
于 2016-08-13T19:56:44.653 回答
2
更新： 我现在看到我的回答并没有直接回答你的问题。如果它被证明有用，我会把它留在这里，但它不需要投票。如果没有用，我会删除它。我确实同意@nhahtdh，但是，当他建议“将所有其他节点作为根节点重用您的算法”时。
有人怀疑面试官在这里是为了递归。不要让他失望！
给定一个节点，您的例程应该针对它的每个子节点调用自身（如果有），然后将节点自己的数据添加到返回值，然后返回总和。
为了获得额外的荣誉，请警告面试官，如果用于一般图而不是二叉树，您的例程可能会失败，进入无底、无休止的递归。
于 2012-07-04T11:46:54.437 回答
1
可以将这棵树简化为加权图 G，其中每个边权重 = 其每个节点中值的总和。
然后，在图 G 上运行 Floyd-Warshall 算法。通过检查结果矩阵中的元素，我们可以获得总和等于所需总和的所有节点对。
另外，请注意，算法给出的最短路径也是这棵树中 2 个节点之间的唯一路径。
这只是另一种方法，不如递归方法有效。
于 2012-07-04T15:37:32.887 回答
1
我们可以用树结构动态规划来解决，时间和空间复杂度都是O(n^2)，其中n是所有树节点的个数。
思路如下：
对于树节点，我们保留一个集合，记录从 u 开始到其所有后代的所有可能和。然后递归地，任何节点的集合都可以由它的两个孩子更新，特别是通过合并两个孩子的集合。
伪代码是：
bool findPath(Node u, Set uset, int finalSum) {
Set lset, rset;
if (findPath(u.left, lset, finalSum) || findPath(u.right, rset, finalSum)) return true;
for (int s1 : lset) {
if (finalSum - u.val - s1 == 0 || rset.contains(finalSum - u.val - s1)) return true;
// first condition means a path from u to some descendant in u's left child
// second condition means a path from some node in u's left child to some node in u's right child
uset.insert(s1 + u.val); // update u's set
}
for (int s2 : rset) {
if (finalSum - u.val - s2 == 0) return true;
// don't forget the path from u to some descendant in u's right child
uset.insert(s2 + u.val); // update u's set
}
return false;
}
我注意到最初的问题是查找所有路径，但上面的算法是查找是否存在。我认为这个想法是相似的，但是这个版本使问题更容易解释:)
于 2014-08-17T12:00:22.193 回答
0
public void printPath(N n) {
printPath(n,n.parent);
}
private void printPath(N n, N endN) {
if (n == null)
return;
if (n.left == null && n.right == null) {
do {
System.out.print(n.value);
System.out.print(" ");
} while ((n = n.parent)!=endN);
System.out.println("");
return;
}
printPath(n.left, endN);
printPath(n.right, endN);
}
您可以打印树路径结束 n 节点。像这样 printPath(n);
于 2013-03-22T06:41:13.373 回答
0
void printpath(int sum,int arr[],int level,struct node * root)
{
int tmp=sum,i;
if(root == NULL)
return;
arr[level]=root->data;
for(i=level;i>=0;i--)
tmp-=arr[i];
if(tmp == 0)
print(arr,level,i+1);
printpath(sum,arr,level+1,root->left);
printpath(sum,arr,level+1,root->right);
}
void print(int arr[],int end,int start)
{
int i;
for(i=start;i<=end;i++)
printf("%d ",arr[i]);
printf("\n");
}
复杂度(n logn) 空间复杂度(n)
于 2014-10-26T08:45:20.220 回答
0
# include<stdio.h>
# include <stdlib.h>
struct Node
{
int data;
struct Node *left, *right;
};
struct Node * newNode(int item)
{
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print(int p[], int level, int t){
int i;
for(i=t;i<=level;i++){
printf("\n%d",p[i]);
}
}
void check_paths_with_given_sum(struct Node * root, int da, int path[100], int level){
if(root == NULL)
return ;
path[level]=root->data;
int i;int temp=0;
for(i=level;i>=0;i--){
temp=temp+path[i];
if(temp==da){
print(path,level,i);
}
}
check_paths_with_given_sum(root->left, da, path,level+1);
check_paths_with_given_sum(root->right, da, path,level+1);
}
int main(){
int par[100];
struct Node *root = newNode(10);
root->left = newNode(2);
root->right = newNode(4);
root->left->left = newNode(1);
root->right->right = newNode(5);
check_paths_with_given_sum(root, 9, par,0);
}
这工作......
于 2014-12-08T09:41:26.617 回答
0
我已经尝试了一个答案，期待代码审查。我的代码和审阅者应该是有用的来源。
于 2014-12-26T22:54:38.783 回答
0
下面是使用递归的解决方案。我们执行二叉树的顺序遍历，当我们向下移动一个级别时，我们通过将当前级别的权重添加到树的先前级别的权重来总结总路径权重，如果我们达到我们的总和，我们然后打印出路。此解决方案将处理沿任何给定路径路径可能有多个解决方案的情况。
假设你有一棵以根为根的二叉树。
#include <iostream>
#include <vector>
using namespace std;
class Node
{
private:
Node* left;
Node* right;
int value;
public:
Node(const int value)
{
left=NULL;
right=NULL;
this->value=value;
}
void setLeft(Node* left)
{
this->left=left;
}
void setRight(Node* right)
{
this->right = right;
}
Node* getLeft() const
{
return left;
}
Node* getRight() const
{
return right;
}
const int& getValue() const
{
return value;
}
};
//get maximum height of the tree so we know how much space to allocate for our
//path vector
int getMaxHeight(Node* root)
{
if (root == NULL)
return 0;
int leftHeight = getMaxHeight(root->getLeft());
int rightHeight = getMaxHeight(root->getRight());
return max(leftHeight, rightHeight) + 1;
}
//found our target sum, output the path
void printPaths(vector<int>& paths, int start, int end)
{
for(int i = start; i<=end; i++)
cerr<<paths[i]<< " ";
cerr<<endl;
}
void generatePaths(Node* root, vector<int>& paths, int depth, const int sum)
{
//base case, empty tree, no path
if( root == NULL)
return;
paths[depth] = root->getValue();
int total =0;
//sum up the weights of the nodes in the path traversed
//so far, if we hit our target, output the path
for(int i = depth; i>=0; i--)
{
total += paths[i];
if(total == sum)
printPaths(paths, i, depth);
}
//go down 1 level where we will then sum up from that level
//back up the tree to see if any sub path hits our target sum
generatePaths(root->getLeft(), paths, depth+1, sum);
generatePaths(root->getRight(), paths, depth+1, sum);
}
int main(void)
{
vector<int> paths (getMaxHeight(&root));
generatePaths(&root, paths, 0,0);
}
空间复杂度取决于树的高度，假设这是一棵平衡树，那么基于递归堆栈的深度，空间复杂度为 0(log n)。时间复杂度 O(n Log n) - 基于平衡树，其中每个级别有 n 个节点，并且在每个级别将完成 n 工作量（对路径求和）。我们还知道平衡二叉树的树高以 O(log n) 为界，因此平衡二叉树上每个级别完成的工作量为 O(n log n)
于 2015-01-12T16:47:12.710 回答
0
// assumption node have integer value other than zero
void printAllPaths(Node root, int sum , ArrayList<Integer> path) {
if(sum == 0) {
print(path); // simply print the arraylist
}
if(root ==null) {
//traversed one end of the tree...just return
return;
}
int data = root.data;
//this node can be at the start, end or in middle of path only if it is //less than the sum
if(data<=sum) {
list.add(data);
//go left and right
printAllPaths(root.left, sum-data , path);
printAllPaths(root.right, sum-data , path);
}
//note it is not else condition to ensure root can start from anywhere
printAllPaths(root.left, sum , path);
printAllPaths(root.right, sum , path);
}
于 2015-01-30T22:01:42.933 回答
0
我改进了 Arvind Upadhyay 回答的一些编码逻辑。一旦 if 循环完成，您就不能使用相同的列表。所以需要创建新列表。此外，需要保持逻辑从当前节点下降到搜索路径的级别计数。如果我们没有找到路径，那么在去它的孩子之前，我们需要从递归调用中出来等于 count 次。
int count =0;
public void printAllPathWithSum(Node node, int sum, ArrayList<Integer> list)
{
if(node == null)
return;
if(node.data<=sum)
{
list.add(node.data);
if(node.data == sum)
print(list);
else
{
count ++;
printAllPathWithSum(node.left, sum-node.data, list);
printAllPathWithSum(node.right, sum-node.data, list);
count --;
}
}
if(count != 0)
return ;
printAllPathWithSum(node.left, this.sum, new ArrayList());
if(count != 0)
return;
printAllPathWithSum(node.right, this.sum, new ArrayList());
}
public void print(List list)
{
System.out.println("Next path");
for(int i=0; i<list.size(); i++)
System.out.print(Integer.toString((Integer)list.get(i)) + " ");
System.out.println();
}
查看完整代码：https ://github.com/ganeshzilpe/java/blob/master/Tree/BinarySearchTree.java
于 2015-06-29T22:51:17.943 回答
0
搜索：
Recursively traverse the tree, comparing with the input key, as in binary search tree.
If the key is found, move the target node (where the key was found) to the root position using splaysteps.
Pseudocode:
Algorithm: search (key)
Input: a search-key
1. found = false;
2. node = recursiveSearch (root, key)
3. if found
4. Move node to root-position using splaysteps;
5. return value
6. else
7. return null
8. endif
Output: value corresponding to key, if found.
Algorithm: recursiveSearch (node, key)
Input: tree node, search-key
1. if key = node.key
2. found = true
3. return node
4. endif
// Otherwise, traverse further
5. if key < node.key
6. if node.left is null
7. return node
8. else
9. return recursiveSearch (node.left, key)
10. endif
11. else
12. if node.right is null
13. return node
14. else
15. return recursiveSearch (node.right, key)
16. endif
17. endif
Output: pointer to node where found; if not found, pointer to node for insertion.
于 2016-02-19T10:32:41.040 回答
0
因为我们需要 sum == k 的路径。我假设最坏情况的复杂性可以是 O(total_paths_in_tree) 。
那么为什么不生成每条路径并检查总和，反正它是一棵有负数的树，甚至不是二叉搜索树。
struct node{
int val;
node *left,*right;
node(int vl)
{
val = vl;
left = NULL;
right = NULL;
}
};
vector<vector<int> > all_paths;
vector<vector<int> > gen_paths(node* root)
{
if(root==NULL)
{
return vector<vector<int> > ();
}
vector<vector<int> > left_paths = gen_paths(root->left);
vector<vector<int> > right_paths = gen_paths(root->right);
left_paths.push_back(vector<int> ()); //empty path
right_paths.push_back(vector<int> ());
vector<vector<int> > paths_here;
paths_here.clear();
for(int i=0;i<left_paths.size();i++)
{
for(int j=0;j<right_paths.size();j++)
{
vector<int> vec;
vec.clear();
vec.insert(vec.end(), left_paths[i].begin(), left_paths[i].end());
vec.push_back(root->val);
vec.insert(vec.end(), right_paths[j].begin(), right_paths[j].end());
paths_here.push_back(vec);
}
}
all_paths.insert(all_paths.end(),paths_here.begin(),paths_here.end());
vector<vector<int> > paths_to_extend;
paths_to_extend.clear();
for(int i=0;i<left_paths.size();i++)
{
paths_to_extend.push_back(left_paths[i]);
paths_to_extend[i].push_back(root->val);
}
for(int i=0;i<right_paths.size();i++)
{
paths_to_extend.push_back(right_paths[i]);
paths_to_extend[paths_to_extend.size()-1].push_back(root->val);
}
return paths_to_extend;
}
为了生成路径，我生成了所有左路径和所有右路径，并将 left_paths + node->val + right_paths 添加到每个节点的 all_paths 中。并发送了仍然可以扩展的路径。即来自双方的所有路径+节点。
于 2017-03-03T10:30:02.947 回答
0
这是一个 O(N) 解决方案
int fn(root, sum, *count)
{
if(root == NULL)
return 0;
int left = fn(root->left, sum, count);
int right = fn(root->left, sum, count);
if(left == sum)
*count++;
if(right == sum)
*count++;
if((root->data + left + right) == sum)
*count++;
return (root->data + left + right);
}
于 2020-05-25T13:32:48.563 回答