[劍指offer] 二叉樹中和為某一值的路徑

題目描述

輸入一顆二叉樹和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。

解題思路

用前序周遊的方式通路到某一結點時，把該結點添加到路徑上，并用目标值減去該節點的值。如果該結點為葉結點并且目标值減去該節點的值剛好為0，則目前的路徑符合要求，我們把加入res數組中。如果目前結點不是葉結點，則繼續通路它的子結點。目前結點通路結束後，遞歸函數将自動回到它的父結點。是以我們在函數退出之前要在路徑上删除目前結點，以確定傳回父結點時路徑剛好是從根結點到父結點的路徑。

參考代碼

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<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
    ArrayList<Integer> temp = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null)
            return res;
        target -= root.val;
        temp.add(root.val);
        if(target == 0 && root.left == null && root.right == null)
            res.add(new ArrayList<Integer>(temp));
        else{
            FindPath(root.left, target);
            FindPath(root.right, target);
        }
        temp.remove(temp.size()-1);
        return res;
    }        
}