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

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

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

描述

示例1

輸入：

{10,5,12,4,7},22
           

傳回值：

[[10,5,7],[10,12]]
           

示例2

{10,5,12,4,7},15
           

[]
           

解析

首先分析這道題的傳回值，它是一個二維數組，其中的每個一維數組對應二叉樹中的一條路徑；即路徑是一維數組，結果集是二維數組（又說了一遍????）

// 路徑，一維數組
    private ArrayList<Integer> path = new ArrayList<>();
    // 結果集，二維數組
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
           

然後再進行過程的分析，本題的核心是二叉樹的深度搜尋，同時需要在到達某一點時判斷路徑上的值是否符合目标值，即過程為

1. 對二叉樹進行深度優先周遊
2. 在周遊時記錄到達目前節點的路徑
3. 判斷路徑上的值是否符合目标值

同時，在判斷路徑是否符合目标值時，也有三種情況

1. 到目前節點時，路徑值大于目标值，已經不符合條件，則直接傳回，不用繼續深入
2. 到目前節點時，正好達成目标值，則将目前路徑加入結果集然後傳回，不用繼續深入（此處考慮本題的節點不包含0）
3. 到目前節點時，路徑值小于目标值，則将目前節點加入路徑後，繼續周遊子節點

此外，還需要進行回溯操作，即周遊完某一節點下可能的路徑後，要将其從路徑中删除，這樣才能正确地繼續周遊該節點的兄弟節點！

代碼清單

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 {
    // 路徑，一維數組
    private ArrayList<Integer> path = new ArrayList<>();
    // 結果集，二維數組
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        // 如果目前節點為空，即這條路走到底了，傳回
        if(root == null) return result;
        // 用目标值減去目前節點值，檢視是否滿足
        target = target - root.val;
        // 走過頭了，這個節點後面的路也不用走了
        if(target < 0)
            return result;
        // 将目前節點加入路徑
        path.add(root.val);
        // 滿足條件，且目前是葉子結點，這條路徑就是正确的！
        if(target == 0 && root.left == null && root.right ==null){
            // 把目前的路徑加入到結果集中
            // 此處不能直接 add(path)，要克隆一個出來！
            result.add(new ArrayList<Integer>(path));
            // 關鍵一步！
            // 通過删除目前路徑中的目前節點，回溯到目前節點的父節點繼續找！
            path.remove(path.size()-1);
            return result;
        }
        // 以上都不滿足，說明 target > 0，繼續走
        FindPath(root.left,target);
        FindPath(root.right,target);
        // 同理，傳回前回溯到父節點
        path.remove(path.size()-1);
        return result;
    }
}
           

其中還遇到了一個問題，即将符合條件的路徑加入結果集時，一開始使用的是

result.add(path);
           

這樣的話加入到結果集的是

path

本身，也就是說在修改

path

時

result

中的内容也會被改變，且如果加入兩次，則這兩次都是同一個

path

（可以了解為加進結果集的是指針）！

result.add(new ArrayList<Integer>(path));
           

總結