剑指offer - 二叉树中和为某一值的路径(Java实现)
思路一:首先纠正一个错误,此题目要求按照字典序打印出二叉树中的结点,刚开始使用层序遍历来保存符合要求的路径,然后就一直在处理排序的问题,实际上这个题只要按照前序遍历的方式来求出符合条件路径,输出的时候自动就是按照字典序输出的。综上所述我们只需要对给出的数进行一个前序遍历,这样我们通过递归的方式就可以将符合条件的路径记录出来。
import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<Integer> list1 = new ArrayList<>(); ArrayList<ArrayList<Integer>> list = new ArrayList<>(); solve(root, target, list1, list); return list; } public static void solve(TreeNode root,int target, ArrayList<Integer> list1, ArrayList<ArrayList<Integer>> list) { if(root == null || target < 0) return ; if(target == root.val && root.left == null && root.right == null) {//到达叶子结点 list1.add(root.val); list.add(list1); return ; } list1.add(root.val); solve(root.left, target - root.val, new ArrayList<>(list1), list);//这里需要new新的对象来保存当前结果 solve(root.right, target - root.val, new ArrayList<>(list1), list); //如果不new新的对象,后面的操作就会操作当前的对象,那么当下的list的这种状态将不会被保存, //在我们进行回溯的时候就无法到达我们想到得到的状态。 } }
思路二:我们可以使用迭代的方式来对这课二叉树进行前序遍历。
import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); if(root == null) return ans; Stack<Node> stk = new Stack<>(); stk.push(new Node(0, root, new ArrayList<>())); while(stk.size() > 0) { Node now = stk.pop(); //当前根节点 if(now.sum + now.node.val > target) continue; if(now.sum + now.node.val == target && now.node.left == null && now.node.right == null) { now.list.add(now.node.val); ans.add(now.list); continue; } now.list.add(now.node.val); if(now.node.right != null) { //先将右子树压栈 stk.push(new Node(now.sum + now.node.val, now.node.right, new ArrayList<>(now.list))); } if(now.node.left != null) {//再将左子树压栈 stk.push(new Node(now.sum + now.node.val, now.node.left, new ArrayList<>(now.list))); //这里new对象和递归中的思路相似,如果直接传入对象,那么直接修改堆中值将影响之前的状态。 } } return ans; } } class Node { //保存当前状态下的各个值 ArrayList<Integer> list; //路径 TreeNode node; //结点 int sum; //路径和 public Node(int sum, TreeNode node, ArrayList<Integer> list) { this.sum = sum; this.node = node; this.list = list; } }
思路三:使用的是刚开始层序遍历的思路,类似于算法竞赛中我们经常使用的 bfs,但是这种方式,我们无法对最终的结果进行排序,所以在此题目中我们无法使用这种方法来通过题目,但是这里的代码我还是贴在下面。
import java.util.*; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { ArrayList<ArrayList<Integer>> ans = new ArrayList<>(); if(root == null) return ans; Stack<Node> stk = new Stack<>(); stk.push(new Node(0, root, new ArrayList<>())); while(stk.size() > 0) { Node now = stk.pop(); if(now.sum + now.node.val > target) continue; if(now.sum + now.node.val == target && now.node.left == null && now.node.right == null) { now.list.add(now.node.val); ans.add(now.list); continue; } now.list.add(now.node.val); if(now.node.left != null) { stk.push(new Node(now.sum + now.node.val, now.node.left, new ArrayList<>(now.list))); } if(now.node.right != null) { stk.push(new Node(now.sum + now.node.val, now.node.right, new ArrayList<>(now.list))); } } return ans; } } class Node { ArrayList<Integer> list; TreeNode node; int sum; public Node(int sum, TreeNode node, ArrayList<Integer> list) { this.sum = sum; this.node = node; this.list = list; } }
【剑指offer】题目全解 文章被收录于专栏
本专栏主要是刷剑指offer的题解记录