剑指offer最优解Java版-二叉树中和为某一值的路径

题目描述

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

解决方法

深搜遍历，如果找到符合条件的链表，加入全局链表集合中。

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

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

    }

}

public class Solution {
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
    private ArrayList<Integer>            list    = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) return listAll;
        list.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null){
            // 一定要是深拷贝
            listAll.add(new ArrayList<>(list));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        // 深搜后清除当前节点
        list.remove(list.size() - 1);
        return listAll;
    }
}

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(n²)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我