以下はインタビューの質問です。
各ノードに値が含まれるバイナリ ツリー (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 に答える
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 に答える
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);
}
You can print tree path end the n node. like this printPath(n);
于 2013-03-22T06:41:13.373 に答える
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
以下は、再帰を使用したソリューションです。バイナリ ツリーのトラバーサルを順番に実行し、レベルを下に移動すると、現在のレベルの重みをツリーの前のレベルの重みに追加することにより、パスの重みの合計を合計します。合計に達すると、次に出力します道を外れます。このソリューションは、特定のパス パスに沿って複数のソリューションが存在する可能性があるケースを処理します。
ルートをルートとするバイナリ ツリーがあるとします。
#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) で制限されることもわかっているため、バランスの取れたバイナリ ツリーの各レベルで n 個の作業を行うと、O( n log n) の実行時間が得られます。
于 2015-01-12T16:47:12.710 に答える
0
コードレビューを期待して、回答を試みました。私のコードとレビュアーは役立つ情報源になるはずです。
于 2014-12-26T22:54:38.783 に答える
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
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
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
// 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 に答える