剑指 Offer 34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:

给定如下二叉树，以及目标和 target = 22，

          5

         / \

        4   8

       /   / \

      11  13  4

     /  \    / \

    7    2  5   1

[

   [5,4,11,2],

   [5,8,4,5]

]

提示：

节点总数 <= 10000

做题思路：

首先明白这道题要求的是对树进行一次遍历，然后在遍历的时候记录从根节点到当前节点的路径和，以防止重复计算。所以可以采用深度搜索的方式，初始化LinkedList<List> res，然后递归查找不同节点，如果路径和等于target或者root.left为空或者root.right为空，则将查找的路径和的各个节点加入res即可，然后最后返回res。

class Solution {

    LinkedList<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        recur(root, target, new LinkedList<>());

        return res;

    }

    void recur(TreeNode root, int target, LinkedList<Integer> path) {

        if (root == null) return;

        path.add(root.val);

        if (getSum(path) == target && root.left == null && root.right == null)

            res.add(new LinkedList(path));

        recur(root.left, target, path);//递归左节点

        recur(root.right, target, path);//递归右节点

        path.removeLast(); //向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.removeLast() 。

    }

    int getSum(LinkedList<Integer> list) {//求得路径和

        int sum = 0;

        for (int i : list) sum += i;

        return sum;

    }

}

这是k神更为简洁的代码可以借鉴一下，因为若单独写一个 getSum() 函数，则会产生不必要的额外计算。

算法流程：

pathSum(root, sum)函数：

初始化：结果列表 res ，路径列表 path 。
返回值：返回 res 即可。

recur(root, tar)recur(root, tar) 函数：
递推参数：当前节点 root ，当前目标值 tar 。
终止条件：若节点 root 为空，则直接返回。
递推工作：
- 路径更新：将当前节点值 root.val 加入路径 path ；
- 目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 00 ）；
- 路径记录：当 ① root 为叶节点且 ② 路径和等于目标值，则将此路径 path 加入 res 。
- 先序遍历：递归左 / 右子节点。
- 路径恢复：向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。

class Solution {

    LinkedList<List<Integer>> res = new LinkedList<>();

    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        recur(root, sum);

        return res;

    }

    void recur(TreeNode root, int tar) {

        if(root == null) return;

        path.add(root.val);

        tar -= root.val;

        if(tar == 0 && root.left == null && root.right == null)

            res.add(new LinkedList(path));

        recur(root.left, tar);

        recur(root.right, tar);

        path.removeLast();

    }

}

这个是官方题解，与k神的代码不同，一个是LinkedList，一个Deque。

class Solution {

    List<List<Integer>> ret = new LinkedList<List<Integer>>();

    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        dfs(root, target);

        return ret;

    }

    public void dfs(TreeNode root, int target) {

        if (root == null) {

            return;

        }

        path.offerLast(root.val);

        target -= root.val;

        if (root.left == null && root.right == null && target == 0) {

            ret.add(new LinkedList<Integer>(path));

        }

        dfs(root.left, target);

        dfs(root.right, target);

        path.pollLast();

    }

}

参考链接：

https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/

巴特西

剑指 Offer 34. 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径

最新文章

热门文章