Ниже приведен собеседование.
Вам предоставляется двоичное дерево (не обязательно BST), в котором каждый node содержит значение. Создайте алгоритм для печати всех путей, которые суммируются до этого значения. Обратите внимание, что это может быть любой путь в дереве - ему не нужно начинать в корне.
Хотя я могу найти все пути в дереве, которые начинаются с корня, имеют заданную сумму, я не могу это сделать для путей, не начинающихся с корня.
Ну, это дерево, а не график. Итак, вы можете сделать что-то вроде этого:
псевдокод:
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)
Возможно, вам придется подумать об этом на секунду (я занят другими вещами), но в основном это должен вести тот же алгоритм, который внедряется в каждом node в дереве
EDIT: это фактически дает только "конец node". Однако, поскольку это дерево, вы можете просто начать с этих конечных узлов и вернуться назад, пока не получите требуемую сумму.
ИЗМЕНИТЬ 2: и, конечно, если все значения положительны, вы можете прервать спуск, если ваша текущая суммa >= требуемая.
Здесь ответ O(n + numResults) (по сути тот же, что и @Somebody, но со всеми проблемами):
cumulativeSumBeforeNode.cumulativeSumBeforeNode (значение в этом ключе будет списком узлов).cumulativeSumBeforeNode и целевой суммой. Посмотрите эту разницу в хэш-таблицу.cumulativeSumBeforeNode в хеш-таблице.код:
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;
}
}
}
Основываясь на христианском ответе выше:
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, "");
Вот подход с сложностью nlogn.
Hashmap<CumulativeSum, reference to the corresponding node>.SUM.SUM-K в HashMap.HashMap.Чистое решение в 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;
}
Обновление: теперь я вижу, что мой ответ напрямую не отвечает на ваш вопрос. Я оставлю его здесь, если он окажется полезным, но ему не нужно повышать. Если это не полезно, я удалю его. Однако я согласен с @nhahtdh, когда он советует: "Повторите свой алгоритм со всеми остальными узлами как root".
Один подозревает, что интервьюер ловит рыбу для рекурсии. Не разочаровывай его!
Учитывая node, ваша подпрограмма должна вызывать себя против каждого из своих дочерних узлов, если она есть, а затем добавить собственную привязку node к возвращаемым значениям, а затем вернуть сумму.
Для получения дополнительной информации предоставьте интервьюеру, что ваша программа может выйти из строя, введя бесконечную бесконечную рекурсию, если она используется на общем графике, а не на двоичном дереве.
Можно уменьшить это дерево до взвешенного графа G, где каждый вес края = сумма значений в каждом из его узлов.
Затем запустите алгоритм Флойда-Варшалла на графе G. Проверяя элементы в полученной матрице, мы можем получить все пары узлов, между которыми общая сумма равна искомой сумме.
Также обратите внимание, что кратчайший путь, который дает алгоритм, также является единственным путем между двумя узлами в этом дереве.
Это еще один подход, не такой эффективный, как рекурсивный подход.
Мы можем решить это с помощью динамического программирования древовидной структуры, а также сложность времени и пространства - это O (n ^ 2), где n - число всех узлов дерева.
Идея такова:
Для дерева node мы сохраняем набор, записывающий все возможные суммы, начиная с u и всех его потомков. Затем рекурсивно любой набор node может быть обновлен двумя его дочерними элементами, в частности, путем слияния двух дочерних наборов.
Псевдокод:
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 left child
// second condition means a path from some node in u left child to some node in u right child
uset.insert(s1 + u.val); // update u 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 right child
uset.insert(s2 + u.val); // update u set
}
return false;
}
Я замечаю, что исходный вопрос состоит в том, чтобы найти все пути, но вышеприведенный алгоритм должен найти, существует ли. Я думаю, что идея схожа, но эта версия упрощает объяснение проблемы:)
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 node. например, printPath (n);
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)
# 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);
}
Это работает.....
Я попытался ответить, ожидая обзора кода. Мой код, а также рецензенты должны быть полезными.
Ниже приведено решение с использованием рекурсии. Мы выполняем обход бинарного дерева, когда мы перемещаемся вниз по уровню, суммируем общий вес путя, добавляя вес текущего уровня к весам предыдущих уровней дерева, если мы нажмем на нашу сумму, тогда мы напечатаем из пути. Это решение будет обрабатывать случаи, когда у нас может быть более одного решения по любому пути пути.
Предположим, что у вас есть двоичное дерево, корневое в корне.
#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)
// 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);
}
Я улучшил некоторую логику кодирования ответа Арвинда Упадхая. После выполнения цикла if вы не можете использовать тот же список. Поэтому нужно создать новый список. Кроме того, необходимо поддерживать подсчет уровня, по которому логика переходит из текущего node в путь поиска. Если мы не находим путь, поэтому перед тем, как идти к его детям, нам нужно выйти из рекурсивного вызова, равного количеству отсчетов.
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
Поиск:
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.
Так как нам нужны пути, имеющие сумму == 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 в каждом node. И отправили пути, которые все еще могут быть расширены .i.e все пути с обеих сторон + node.