剑指offer - 输入一个整数，在二叉树中返回路径和为这个整数的所有路径

非递归版

static class Node { int val; Node left; Node right; public Node(int val) { super(); this.val = val; } } public static void printEdge(Node root, int target) { if (root == null) { return; } List<Node> passed = new ArrayList<>(); // 储存路径 Stack<Node> help = new Stack<>(); // 储存右孩子节点 int sum = 0; while (root != null || !help.isEmpty()) { if (root == null) { root = help.pop(); Node tmp; while (!passed.isEmpty() && (tmp = passed.get(passed.size() - 1)).right != root) { passed.remove(passed.size() - 1); sum -= tmp.val; } } sum += root.val; passed.add(root); if (sum == target) { for (Node n : passed) { System.out.print(n.val + "-->"); } System.out.println(); } if (root.right != null) { help.push(root.right); } root = root.left; } } public static void main(String[] args) { Node n1 = new Node(10); Node n2 = new Node(5); Node n3 = new Node(12); Node n4 = new Node(4); Node n5 = new Node(7); n1.left = n2; n1.right = n3; n2.left = n4; n2.right = n5; printEdge(n1, 22); System.out.println("---------------------"); printEdge(n1, 15); System.out.println("---------------------"); printEdge(n1, 10); System.out.println("---------------------"); printEdge(n1, 100); }

递归版

public static void printEdge(Node root, int target, List<Node> passed) { if (root == null) { return; } target -= root.val; passed.add(root); if (target == 0) { for (Node n : passed) { System.out.print(n.val + "--->"); } System.out.println(); } printEdge(root.left, target, passed); printEdge(root.right, target, passed); if (!passed.isEmpty()) { passed.remove(passed.size() -1); } }