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

24.二叉树中和为某一值的路径

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

路径问题就直接递归就行了，用一个list存储当前路径，如果成功就加入答案集，不成功就删除最后一个结点回溯。
这里还要用sort比较一下，Collections.sort(all, ((o1, o2) -> o2.size() - o1.size()))，比较的时候就是降序排列。

代码

  public class TreeNode {

  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

  public TreeNode(int val) {
    this.val = val;

  }

}

public void find(TreeNode root, int target, ArrayList<ArrayList<Integer>> all, ArrayList list) {
  if (root == null) {
    return;
  }
  int value = root.val;
  list.add(value);
  if (target == value && root.left == null && root.right == null) {
    all.add(new ArrayList<>(list));
  } else {
    find(root.left, target - value, all, list);
    find(root.right, target - value, all, list);
  }
  list.remove(list.size() - 1);
}

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
  ArrayList<ArrayList<Integer>> all = new ArrayList<>();
  ArrayList<Integer> list = new ArrayList<>();
  find(root, target, all, list);
  Collections.sort(all, ((o1, o2) -> o2.size() - o1.size()));
  return all;
}