java - 在二叉树中具有特定和的叶子路径

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