剑指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的题解记录
查看18道真题和解析
