查找二叉树中所有等于总和的路径

[2,3,5,4,8,6，-2，null，null，null， NULL，NULL，NULL，NULL，2]和总和= 7

打印：[3,4]，[2,5]，[2,5，-2,2]

我可以拿出一个^ 2解决方案，但有没有更好的解决方案呢？也许有一些额外的内存，如使用堆栈或哈希表。

我已经花了4小时试图想出一些解决方案，但所有的解决方案变得太丑陋或混乱。

我的n^2解决方案比较简单： 1）有一个方法，即递归调用自己直到所有叶子的助手。当它找到总和的路径时，将它添加到结果中。（这是将采取为O（n）） 2）呼叫为每个节点此方法在树（O（N）*为O（n）= O（N^2））

我的简单的解决方案

//TreeNode structure 
public class TreeNode { 
    int val; 
    public TreeNode left; 
    public TreeNode right; 
    TreeNode(int x) { val = x; } 
    } 

//Solution class 
public class Solution { 

    public List<List<Integer>> pathSum(TreeNode root, int sum) { 

     List<Integer> temp = new ArrayList<Integer>(); 
     List<List<Integer>> result = new ArrayList<>(); 

     if (root == null) return result; 
     Queue<TreeNode> q = new LinkedList<>(); 

     q.offer(root); 


     while (!q.isEmpty()) 
     { 
      TreeNode top = q.poll(); 
      helper(top,sum,temp,result); 

      if (top.left != null) q.offer(top.left); 
      if (top.right != null) q.offer(top.right); 
     } 


     return result; 
    } 

    public void helper(TreeNode root, int sum, List<Integer> temp, List<List<Integer>> result) 
    { 


    if (root == null) return; 
    temp.add(root.val) ; 
    if (root.val == sum) 
    { 

     result.add(new ArrayList<>(temp)); 
    } 

    helper(root.left,sum-root.val, temp, result); 
    helper(root.right, sum-root.val, temp, result); 

    temp.remove(temp.size() - 1); 

    } 

    } 

//Execution class 
public class treeApp { 

public static void main(String args[]) 
{ TreeNode root = new TreeNode(2); 
    root.left = new TreeNode(3); 
    root.right = new TreeNode(5); 

    root.left.left = new TreeNode(4); 
    root.left.right = new TreeNode(8); 

    root.right.left = new TreeNode(6); 
    root.right.right = new TreeNode(-2); 

    root.right.right.right = new TreeNode(2); 

    Solution sol = new Solution(); 

    List<List<Integer>> result ; 
    result = sol.pathSum(root, 7); 

    for (List l : result) 
    { 
     System.out.println(l.toString()); 
    } 

} 
//Prints: 
[2, 5] 
[2, 5, -2, 2] 
[3, 4]

来源

2017-03-10 Snehasis Ghosh

导线在任何方便的方式在树（广度优先或深度优先），但包括路径到该节点。

在每个节点处，检查所有的路径的求和为此在该节点;如果任何等于目标值，则将这些路径添加到解决方案（作为功能结果传回）。

然后复发：当前节点添加到路径和每个孩子打电话。

这足够清楚了吗？我认为这可以在更短的时间内解决问题。遍历是O（N）到达所有节点。在每个节点上，您都会走过长度很长的路径。如果你有一个平衡二叉树，深度是O（log2 [N]）。

来源

2017-03-10 17:20:43 Prune

查找二叉树中所有等于总和的路径

回答

相关问题