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

in with 0 comment

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

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
示例 2:

输入:root = [1,2,3], targetSum = 5
输出:[]
示例 3:

输入:root = [1,2], targetSum = 0
输出:[]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 回溯,DFS,从根节点开始遍历二叉树,到叶子节点后剪枝回到上一层再往下走,递归遍历整个树。递归过程中:

    1. 如果节点为空,return
    2. 将 root.val 放入 path 中
    3. target = target - root.val 每下一层都需要更新 target 的值
    4. target == 0 并且 root 是叶子节点(左右子树为空),该路径符合要求,将 path add 到 res 中
    5. 开始递归左子树和右子树
    6. 递归结束后剪枝,path.removeLast()
  2. 回溯,BFS,通过队列依次使节点入队先序遍历二叉树,需要使用 hash 存储每个节点的父节点,使用队列记录到每个节点的总和 sum,左子节点不为空就将左子节点入队,并且将当前节点的 sum 也入队,右子节点同理。如果左右子节点都为空的时候需判断 sum 是否等于 target,不等不是我们需要的结果,相等的时候需要找路径。通过叶子节点和 hash 可以找到从下往上的路径,找路径的时候将 val 放入路径 list 中,最后再将 list 反转添加到 res。

代码

解法一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

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

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recur(root, target);
        return res;
    }

    public void recur(TreeNode root, int target) {
        if (root == null) return;
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) res.add(new LinkedList<>(path));
        recur(root.left, target);
        recur(root.right, target);
        path.removeLast();
    }
}

解法二

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    List<List<Integer>> res = new ArrayList<>();
    Map<TreeNode, TreeNode> map = new HashMap<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> queue2 = new LinkedList<>();
        queue.add(root);
        queue2.add(0);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int sum = queue2.poll() + node.val;
            if (node.left == null && node.right == null) {
                if (sum == target) {
                    List<Integer> tmp = new ArrayList<>();
                    while (node != null) {
                        tmp.add(node.val);
                        node = map.get(node);
                    }
                    Collections.reverse(tmp);
                    res.add(tmp);
                }
            } else {
                if (node.left != null) {
                    queue.add(node.left);
                    queue2.add(sum);
                    map.put(node.left, node);
                }
                if (node.right != null) {
                    queue.add(node.right);
                    queue2.add(sum);
                    map.put(node.right, node);
                }
            }
        }
        return res;
    }
}