113. Path Sum II

题目描述和难度

  • 题目描述：

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

思路分析

求解关键：

参考解答

参考解答1

Java 实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 根节点
        if (root.left == null && root.right == null) {
            if (root.val == sum) {
                List<Integer> temp1 = new ArrayList<>();
                temp1.add(root.val);
                result.add(temp1);
                return result;
            }
        }
        List<List<Integer>> leftLists = pathSum(root.left, sum - root.val);
        mergeOneAndList(root, leftLists, result);
        List<List<Integer>> rightLists = pathSum(root.right, sum - root.val);
        mergeOneAndList(root, rightLists, result);
        return result;
    }

    private void mergeOneAndList(TreeNode node, List<List<Integer>> listList, List<List<Integer>> result) {
        for (int i = 0; i < listList.size(); i++) {
            List<Integer> temp1 = new ArrayList<>();
            temp1.add(node.val);
            temp1.addAll(listList.get(i));
            result.add(temp1);
        }
    }
}

题后总结：使用递归的方法解决问题，很多时候，并不是让我们真正地去做这个问题，而是须要我们发现递归关系，寻找递归终止条件。历史上类似的经典问题有汉诺塔问题和八皇后问题。

但是，我自己觉得，我的解法，尤其是在 mergeOneAndList() 函数的部分稍显复杂。

下面给出一种简洁的解法：这种解法显得更自然一些，遍历了从根结点到叶子结点的每一个结点，然后累加计算加到了多少，这是与老师的思路不同的一种思路。

public class Solution2 {

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        getSum(root, new ArrayList<Integer>(), 0, sum);
        return result;
    }

    private void getSum(TreeNode node, ArrayList<Integer> list, int current, int sum) {
        if (node == null) {
            return;
        }
        current += node.val;
        list.add(node.val);
        if (node.left == null && node.right == null) {
            if (current == sum) {
                result.add(list);
            } else {
                // 什么都不做
                // 在这里可以把不满足的节点都遍历出来
                return;
            }
        }
        if (node.left != null) {
            getSum(node.left, new ArrayList<Integer>(), current, sum);
        }
        if (node.right != null) {
            getSum(node.right, new ArrayList<Integer>(), current, sum);
        }
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0113-path-sum-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。