[[438573]]

Leetcode : https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_27_pathSum/Solution.java

二叉樹中和為某一值的路徑

“題目描述 ：給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)整數(shù)目標(biāo)和 targetSum ，找出所有 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 路徑總和等于給定目標(biāo)和的路徑。難度：中等葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。示例 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 
 
輸出：[] 

解題思路：

“本問題是典型的二叉樹方案搜索問題，使用回溯法解決，其包含 先序遍歷 + 路徑記錄 兩部分。

• 先序遍歷： 按照 “根、左、右” 的順序，遍歷樹的所有節(jié)點(diǎn)。
• 路徑記錄： 在先序遍歷中，記錄從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。當(dāng)路徑為 ① 根節(jié)點(diǎn)到葉節(jié)點(diǎn)形成的路徑 且 ② 各節(jié)點(diǎn)值的和等于目標(biāo)值 sum 時(shí)，將此路徑加入結(jié)果列表。

算法流程：pathSum(root，sum) 函數(shù):

• 初始化：結(jié)果列表res，路徑列表 path.
• 返回值：返回res即可。

recur (root, tar) 函數(shù):

• 遞推參數(shù)：當(dāng)前節(jié)點(diǎn)root，當(dāng)前目標(biāo)值tar 。
• 終止條件：若節(jié)點(diǎn)root為空，則直接返回。
• 遞推工作：
  • 路徑更新：將當(dāng)前節(jié)點(diǎn)值root. val加入路徑path ;
  • 目標(biāo)值更新：tar=tar - root.val(即目標(biāo)值tar從sum減至0);
  • 路徑記錄：當(dāng)①root為葉節(jié)點(diǎn)且②路徑和等于目標(biāo)值，則將此路徑path加入res。
  • 先序遍歷：遞歸左1右子節(jié)點(diǎn)。
  • 路徑恢復(fù)：向上回溯前，需要將當(dāng)前節(jié)點(diǎn)從路徑path中刪除，即執(zhí)行path. pop()。

復(fù)雜度分析：

• 時(shí)間復(fù)雜度 O(N)： N 為二叉樹的節(jié)點(diǎn)數(shù)，先序遍歷需要遍歷所有節(jié)點(diǎn)。
• 空間復(fù)雜度 O(N)： 最差情況下，即樹退化為鏈表時(shí)，path 存儲(chǔ)所有樹節(jié)點(diǎn)，使用 O(N) 額外空間。

package com.nateshao.sword_offer.topic_27_pathSum; 
 
import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.List; 
 
/** 
 * @date Created by 邵桐杰 on 2021/12/1 16:45 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 二叉樹中和為某一值的路徑 
 */ 
public class Solution { 
 
    public static void main(String[] args) { 
        TreeNode node1 = new TreeNode(10); 
        TreeNode node2 = new TreeNode(5); 
        TreeNode node3 = new TreeNode(12); 
        TreeNode node4 = new TreeNode(4); 
        TreeNode node5 = new TreeNode(7); 
 
        node1.left = node2; 
        node1.right = node3; 
        node2.left = node4; 
        node2.right = node5; 
 
        Solution p = new Solution(); 
        System.out.println(p.listAll); 
        p.pathSum(node1, 22); 
        for (List<Integer> list : p.listAll) { 
            for (int i : list) { 
                System.out.print(i + " "); 
            } 
            System.out.println(); 
        } 
        /** 
         * [] 
         * 10 5 7 
         * 10 12 
         */ 
    } 
 
    /****************************** 劍指offer **********************************/ 
 
    private static List<List<Integer>> listAll = new ArrayList<>(); 
    private static List<Integer> list = new ArrayList<>(); 
 
    /** 
     * 思路：先保存根節(jié)點(diǎn)，然后分別遞歸在左右子樹中找目標(biāo)值，若找到即到達(dá)葉子節(jié)點(diǎn)，打印路徑中的值 
     * 
     * @param root 
     * @param target 
     * @return 
     */ 
    public static List<List<Integer>> pathSum(TreeNode root, int target) { 
        if (root == null) return listAll; 
        list.add(root.val); 
        target -= root.val; 
        if (target == 0 && root.left == null && root.right == null) { 
            listAll.add(new ArrayList<>(list)); 
        } 
        pathSum(root.left, target); 
        pathSum(root.right, target); 
        list.remove(list.size() - 1); 
        return listAll; 
    } 
 
 
    /*********************** 精選解答 ***************************/ 
    LinkedList<List<Integer>> res = new LinkedList<>(); 
    LinkedList<Integer> path = new LinkedList<>(); 
 
    public List<List<Integer>> pathSum2(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(); 
    } 
 
 
    public static 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; 
        } 
    } 
}