路径叶其在二叉树特定数额

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)); 
} 

我无法弄清楚如何打印特定的路径。

我的节点类看起来是这样的：

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每个节点的家长，您可以通过获取父在一个循环中找到从根到任何节点（逆转）路径直到它为空。

此外，您的代码为pathSum似乎是混合布尔值和整数，并且您从不检查总和的值。

Answer 3

我建议改变你的MYNODE类包括父节点：

MyNode left; 
MyNode right; 
MyNode parent; 

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

，然后当你击中正确的和一个节点，你可以通过该节点到去通过量的祖先，直到它的另一个功能点击具有空父母（根）的节点。

Answer 4

不错的拼图，我喜欢它。你几乎已经拥有了它，只是对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