Путь к листу с определенной суммой в двоичном дереве

Question

Я знаю, как найти, имеет ли двоичное дерево определенный путь с заданной суммой (если это не лучший способ, пожалуйста, дайте мне знать):

int pathSum(MyNode root, int sum)
{
    if(root == null)
        return -1;
    int temp = sum - root.value;
    return(pathSum(root.left,temp) || pathSum(root.right,temp));
}

Что я не могу понятьэто как распечатать конкретный путь.

Мой класс Node выглядит следующим образом:

class MyNode {
    int value;
    MyNode left;
    MyNode right;

    MyNode(int value)
    {
        this.value = value;
    }
}

Answer 1

Попробуйте, используйте перегрузку:

 public void pathToSum(int sum) {
    pathToSum(root, sum);
}

private boolean pathToSum(Node n, int sum) {
    if (null != n) {
        sum -= n.data;
        boolean found = pathToSum(n.left, sum);

        if (!found) {
            found = pathtoSum(n.right, sum);
        }
        if (found) {
            println(n.data);
                            return found;
        }
    }
    return 0 == sum ? true : false;
}

Этот код протестирован со следующими классами:

import java.util.LinkedList;
import java.util.Queue;
public class BST {
Node root;
public BST(){
    root = null;
}

public void insert(int el){

    Node tmp = root, p=null;
    while(null!=tmp && el != tmp.data){
        p=tmp;
        if(el<tmp.data)
            tmp=tmp.left;
        else
            tmp=tmp.right;
    }
    if(tmp == null){
        if(null == p)
            root = new Node(el);
        else if(el <p.data)
            p.left= new Node(el);
        else
            p.right=new Node(el);
    }
}//

public void pathToSum(int sum) {
    pathToSum(root, sum);
}//

private boolean pathToSum(Node n, int sum) {
    if (null != n) {
        sum -= n.data;
        boolean found = pathToSum(n.left, sum);

        if (!found) {
            found = pathToSum(n.right, sum);
        }
        if (found) {
            System.out.println(n.data);
            return found;
        }
    }
    return 0 == sum ? true : false;
}

public static void main(String[] args){
    int[] input={50,25,75,10,35,60,100,5,20,30,45,55,70,90,102};
    BST bst = new BST();
    for(int i:input)
        bst.insert(i);
    bst.pathToSum(155);
}
}

class Node{
public int data;
public Node left;
public Node right;
public Node(int el){
    data = el;
}
}

Результат:

45
35
25
50

Answer 2

Я предлагаю изменить ваш класс MyNode, чтобы включить родительский узел:

MyNode left;
MyNode right;
MyNode parent;

MyNode(int value, MyNode parent)
{
    this.value = value;
    this.parent = parent;
}

, а затем, когда вы нажмете на узел с правильной суммой, вы можете передать этот узел другой функции, которая проходит через родословную доон попадает на узел с нулевым родителем (корнем).

Answer 3

Хорошая головоломка, мне понравилось.У вас почти это было, просто некоторая путаница с int и boolean, и вы не проверяли условие завершения суммы, равной нулю.

public class NodeSums {

    static boolean pathSum(MyNode root, int sum) {
        boolean ret;
        if (root == null) {
            ret = sum == 0;
        } else {
            int remain = sum - root.value;
            ret = pathSum(root.left,remain) || pathSum(root.right, remain);
        }
        return ret;
    }

    static class MyNode {
        int value;
        MyNode left;
        MyNode right;

        MyNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {

        /**
         * Valid sums will be 3, 8, and 9
         * 
         *    1 -- 2 
         *      --
         *      -- 3 -- 4
         *           --
         *           -- 5
         */
        MyNode root = new MyNode(1);
        root.left = new MyNode(2);
        root.right = new MyNode(3);
        root.right.left = new MyNode(4);
        root.right.right = new MyNode(5);

        for (int i = 1; i < 10; i++) {
            System.out.println("Path sum " + i + " " + pathSum(root, i));
        }
    }
}

Вывод

Path sum 1 false
Path sum 2 false
Path sum 3 true
Path sum 4 false
Path sum 5 false
Path sum 6 false
Path sum 7 false
Path sum 8 true
Path sum 9 true

Answer 4

Если вы храните родительский узел каждого узла в MyNode, вы можете найти (обратный) путь от корня к любому узлу, получая родительский цикл в цикле, пока он не станет нулевым.

Кроме того, ваш кодпоскольку pathSum, кажется, смешивает логические значения и целые числа, и вы никогда не проверяете значение суммы.