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

剑指 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/

上一篇:Java 集合类 总结


下一篇:Java面试题