剑指offer - 二叉树中和为某一值的路径(Java实现)

题目链接：https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&&tqId=11177&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先纠正一个错误，此题目要求按照字典序打印出二叉树中的结点，刚开始使用层序遍历来保存符合要求的路径，然后就一直在处理排序的问题，实际上这个题只要按照前序遍历的方式来求出符合条件路径，输出的时候自动就是按照字典序输出的。综上所述我们只需要对给出的数进行一个前序遍历，这样我们通过递归的方式就可以将符合条件的路径记录出来。

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;
    }
}