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

題目描述

輸入一棵二叉樹和一個(gè)整數(shù)，打印出二叉樹中節(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從樹的根節(jié)點(diǎn)開始往下一直到葉節(jié)點(diǎn)所經(jīng)過的節(jié)點(diǎn)形成一條路徑。

示例：

給定如下二叉樹，以及目標(biāo)和 sum = 22，

image

返回:
[
[5,4,11,2],
[5,8,4,5]
]

提示：

轉(zhuǎn)載來源：力扣（LeetCode）

題目分析

開門見山不叭叭：回溯加深搜

1. 從根節(jié)點(diǎn)開始，使用一個(gè)nowPath記錄當(dāng)前已走路徑，使用一個(gè)nowSum記錄當(dāng)前路徑總和
2. 判斷當(dāng)前節(jié)點(diǎn)是不是葉子節(jié)點(diǎn)
   2.1 如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，判斷當(dāng)前路徑總和是否等于sum，若等于，將{nowPath + 當(dāng)前節(jié)點(diǎn)}加入到result里，若不等，返回
   2.2 如果當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)加入到nowPath，同時(shí)更新nowSum，并繼續(xù)DFS
3. 當(dāng)前節(jié)點(diǎn)的左右子樹都遍歷完畢之后，回溯，將當(dāng)前節(jié)點(diǎn)從nowPath里移除，更新nowSum，返回
4. 返回result

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

    public void search(TreeNode root,int sum,int nowSum,List<Integer> nowPath){ 
        if(root == null) return;
        if(root.left == null
            && root.right == null
            && nowSum + root.val == sum){
            nowPath.add(root.val);
            List<Integer> tmp = new ArrayList<>(nowPath);
            result.add(tmp); 
            nowPath.remove(nowPath.size() - 1);
            return;
        }
        nowPath.add((Integer)root.val);
        search(root.left,sum,nowSum + root.val,nowPath);
        search(root.right,sum,nowSum + root.val,nowPath);
        nowPath.remove(nowPath.size() - 1);
    }