題目描述

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

代碼實(shí)現(xiàn)

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<Integer> path = new ArrayList<>();
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) 
            return list;
        
        //每訪(fǎng)問(wèn)到一個(gè)結(jié)點(diǎn)的時(shí)候，都把當(dāng)前的結(jié)點(diǎn)添加到路徑中去，并調(diào)整target的值
        path.add(root.val);
        target -= root.val;
        
        //已到葉節(jié)點(diǎn)并且和為target，則把當(dāng)前路徑添加到輸出列表里
        //因?yàn)閍dd添加的是引用，如果不new一個(gè)的話(huà)，最終list保存到的只是最后一個(gè)path
        if(target == 0 && root.left == null && root.right == null)
            list.add(new ArrayList<Integer>(path));
       
        //否則繼續(xù)遍歷
        FindPath(root.left, target);
        FindPath(root.right, target);
        
        //已到葉節(jié)點(diǎn)之后會(huì)跳過(guò)兩個(gè)遞歸函數(shù)到這里，此時(shí)要把最后一個(gè)結(jié)點(diǎn)從路徑中刪除，才能返回上層結(jié)點(diǎn)
        path.remove(path.size()-1);
        return list;
    }
}

主要思路

1、這道題有點(diǎn)難度，首先記住一句話(huà)：在樹(shù)的前序、中序、后序遍歷中，只有前序遍歷是首先遍歷根結(jié)點(diǎn)的（因此需要先遍歷根結(jié)點(diǎn)的題，就是考查前序遍歷）
2、代碼注釋里寫(xiě)的比較清楚了，首先就是要把當(dāng)前結(jié)點(diǎn)（首先是根結(jié)點(diǎn)）添加到路徑里，同時(shí)target 減去當(dāng)前結(jié)點(diǎn)的值；然后，如果當(dāng)前結(jié)點(diǎn)為葉節(jié)點(diǎn)并且和也達(dá)到給定值，就把這個(gè)路徑添加到列表，否則就一直遍歷下去；最后，遍歷到葉節(jié)點(diǎn)之后，返回上層結(jié)點(diǎn)之前，一定要把最后一個(gè)結(jié)點(diǎn)從路徑中刪除
3、把符合條件的路徑添加到列表中的時(shí)候，因?yàn)閍dd添加的是引用，如果不是每次都new一個(gè)path的話(huà)，最終list保存到的只是最后一個(gè)path（可以看一下ArrayList的源碼）