剑指offer-24-二叉树中和为某一值的路径

因为result.add(list)是吧list这个对象的引用地址添加到result了，result中的元素就会共用list，而list是我们用来存放当前路径的地方，因此我们需要复制一份之后加入result数组中

如何解决“在返回值的list中，数组长度大的数组靠前”这一问题呢？ 通过将程序中的左右子树搜索顺序交换一下就无法通过了，可见并未排序，只是测试集不全面

请问这步 list.remove(list.size()-1);为什么啊？

非递归的方式： public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Map<ArrayList<Integer>, ArrayList<TreeNode>> treeNodes = new HashMap<>(); ArrayList<Integer> key = new ArrayList<>(); key.add(root.val); if (root.val == target && root.left == null && root.right == null) { result.add(key); return result; } ArrayList<TreeNode> value = new ArrayList<>(); if (root.left != null) { value.add(root.left); } if (root.right != null) { value.add(root.right); } treeNodes.put(key, value); while (treeNodes.size() > 0) { Map<ArrayList<Integer>, ArrayList<TreeNode>> temp = new HashMap<>(); for (ArrayList<Integer> arrayList : treeNodes.keySet()) { ArrayList<TreeNode> tree = treeNodes.get(arrayList); int sum = 0; for (Integer integer : arrayList) { sum += integer; } for (TreeNode treeNode : tree) { ArrayList<Integer> arrayList1 = new ArrayList<>(arrayList); arrayList1.add(treeNode.val); if (sum + treeNode.val == target && treeNode.right == null && treeNode.left == null) { result.add(0, arrayList1); } else { ArrayList<TreeNode> treeNodes1 = new ArrayList<>(); if (treeNode.left != null) { treeNodes1.add(treeNode.left); } if (treeNode.right != null) { treeNodes1.add(treeNode.right); } if (treeNodes1.size() > 0) { temp.put(arrayList1, treeNodes1); } } } } treeNodes = temp; } return result; }

递归就是压栈，自己新建一个栈，通过一个中间量栈帧来实现非递归，对同学的代码略作了修改。 import java.util.ArrayList; import java.util.Stack; public class Solution { public static class StackFrame { public TreeNode node; public int target; public ArrayList<Integer> path; public StackFrame(TreeNode node, int target, ArrayList<Integer> path) { this.node = node; this.target = target; this.path = path; } } public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Stack<StackFrame> stack = new Stack<>(); stack.push(new StackFrame(root, target, new ArrayList<>())); while (!stack.isEmpty()) { StackFrame stackFrame = stack.pop(); stackFrame.path.add(stackFrame.node.val); int rs = stackFrame.target - stackFrame.node.val; if (rs == 0 && stackFrame.node.left == null && stackFrame.node.right == null) { result.add(new ArrayList<>(stackFrame.path)); } if (rs > 0) { if (stackFrame.node.right != null) { stack.push(new StackFrame(stackFrame.node.right, rs, new ArrayList<>(stackFrame.path))); } if (stackFrame.node.left != null) { stack.push(new StackFrame(stackFrame.node.left, rs, new ArrayList<>(stackFrame.path))); } } } return result; } }

题目中要求“按字典序打印”，这个方案中最后是不是要对result进行一次排序操作？

请问ArrayList<arraylist><integer>> result1 = FindPath(root.left, target);的时候。已经到了叶子结点为空返回result了即if(root == null)return result;那么想看右节点合不合适需要进行 ArrayList<arraylist><integer>> result2 = FindPath(root.right, target);但是已经返回result如何进行右节点</integer></arraylist></integer></arraylist>

你能理解list.remove(list.size()-1)么？为什么啊？

为什么前两句的初始化要放在方法外，还要设置成私有呢？

楼主 这个问题: 在返回值的list中，数组长度大的数组靠前，不用考虑吗，迷惑

遇到递归就感觉脑子不够用

好的，后续研究研究更新一下文档

题解里面都能看到你，猛啊老哥

问一下 为什么要执行这一步呀 list.remove(list.size()-1) 是要删除刚添加的数吗 而且这一步在递归后，按道理说，是删除了子递归添加的数据呀

非递归的话，可以自己新增一个栈来管理数据....

只有add方法是这样的吗？

result.add(new ArrayList<integer>(list));这句为什么不能直接result.add(list)</integer>