246.二叉树的路径和 II

描述

给一棵二叉树和一个目标值，设计一个算法找到二叉树上的和为该目标值的所有路径。 路径可以从任何结点出发和结束，但是需要是一条一直往下走的路线。也就是说， 路径上的结点的层级是逐个递增的。

样例

对于二叉树：

            1
           / \
          2   3
         /   /
        4   2

给定目标值6。那么满足条件的路径有两条：

        [
          [2, 4],
          [1, 3, 2]
        ]

思路：

从根结点开始往下遍历二叉树，每遍历一个结点，就把当前结点当做终点，向着根结点往回遍历，返回满足条件的结点， 不可能从 root 开始使用 target-root.val 因为根本不知道路径的起点从哪开始

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        ArrayList<Integer> buffer = new ArrayList<Integer>();
        
        if (root == null) {
            return results;
        }
        
        findSum(root, target, 0, buffer, results);
        return results;
    }

    public void findSum(TreeNode head,
                        int sum,
                        int level,
                        ArrayList<Integer> buffer,
                        List<List<Integer>> results) {
        if (head == null) {
            return;
        }
        
        // target
        int tmp = sum;
        // buffer 数组缓存从上到下的结点值，下标为 level，方便 for 循环中根据 level 获取元素
        buffer.add(head.val);
        // 以当前结点为终点往回寻找，如果找回到根结点仍不满足，终点沿着树向下移动
        for (int i = level; i >= 0; i--) {
            tmp -= buffer.get(i);
            // 将满足的和为sum的连续结点(一条完整路径)加入temp数组
            // 将路径加入results
            if (tmp == 0) {
                List<Integer> temp = new ArrayList<Integer>();
                // 从下往上遍历到 i 层发现和满足目标
                // 从 i 往下遍历到 level 将路线上结点全部加入到 temp
                for (int j = i; j <= level; j++) {
                    temp.add(buffer.get(j));
                }
                results.add(temp);
            }
        }
        
        // 每向下遍历一个结点 level + 1
        findSum(head.left, sum, level + 1, buffer, results);
        findSum(head.right, sum, level + 1, buffer, results);
        // 回溯，当前结点是叶子结点没办法继续往下走了，沿着树往上走
        // 路径中去掉当前结点
        buffer.remove(buffer.size() - 1);
    }
}