題?描述

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

1. 該題路徑定義為從樹的根結點開始往下?直到葉?結點所經過的結點
2. 葉?節點是指沒有?節點的節點
3. 路徑只能從?節點到?節點，不能從?節點到?節點
4. 總節點數?為 n

例如：給出如下二叉樹，sum=22

返回true ，因為存在?條路徑 5 -> 4 -> 11 -> 2 的節點值之和為 22

思路及解答

遞歸回溯法（推薦）

遞歸回溯法是解決這類問題的經典方法：

1. ?前序遍歷?：從根節點開始，先訪問當前節點，再遞歸訪問左右子節點
2. ?路徑記錄?：使用一個列表記錄當前路徑上的節點值
3. ?目標值遞減?：每次遞歸時將目標值減去當前節點值
4. ?葉子節點檢查?：到達葉子節點時檢查剩余目標值是否為0
5. ?回溯處理?：在遞歸返回前需要移除當前節點，以便嘗試其他路徑

public class Solution {
    // 存儲所有符合條件的路徑
    List<List<Integer>> result = new ArrayList<>();
    // 存儲當前路徑
    List<Integer> path = new ArrayList<>();
    
    public List<List<Integer>> FindPath(TreeNode root, int targetSum) {
        if (root == null) {
            return result;
        }
        dfs(root, targetSum);
        return result;
    }
    
    private void dfs(TreeNode node, int remainingSum) {
        if (node == null) {
            return;
        }
        
        // 將當前節點加入路徑
        path.add(node.val);
        remainingSum -= node.val;
        
        // 檢查是否為葉子節點且路徑和等于目標值
        if (node.left == null && node.right == null && remainingSum == 0) {
            result.add(new ArrayList<>(path)); // 必須新建一個ArrayList
        }
        
        // 遞歸處理左右子樹
        dfs(node.left, remainingSum);
        dfs(node.right, remainingSum);
        
        // 回溯，移除當前節點
        path.remove(path.size() - 1);
    }
}

• 時間復雜度：O(n)，n 為?叉樹的節點個數，遍歷完所有的節點
• 空間復雜度：O(n)，借助了額外的空間

迭代法（使用棧模擬遞歸）

使用棧來模擬遞歸過程，避免遞歸帶來的棧溢出風險：

1. ?雙棧結構?：一個棧存儲節點，一個棧存儲剩余目標值
2. ?路徑記錄?：使用鏈表記錄當前路徑，方便回溯
3. ?后進先出?：按照前序遍歷的順序處理節點

public class Solution {
    public List<List<Integer>> FindPath(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Deque<TreeNode> nodeStack = new LinkedList<>();
        Deque<Integer> sumStack = new LinkedList<>();
        Deque<List<Integer>> pathStack = new LinkedList<>();
        
        nodeStack.push(root);
        sumStack.push(targetSum);
        pathStack.push(new ArrayList<>(Arrays.asList(root.val)));
        
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int remainingSum = sumStack.pop();
            List<Integer> currentPath = pathStack.pop();
            
            // 檢查是否為葉子節點且路徑和等于目標值
            if (node.left == null && node.right == null && remainingSum == node.val) {
                result.add(new ArrayList<>(currentPath));
            }
            
            // 右子節點先入棧，保證左子節點先處理
            if (node.right != null) {
                nodeStack.push(node.right);
                sumStack.push(remainingSum - node.val);
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(node.right.val);
                pathStack.push(newPath);
            }
            
            if (node.left != null) {
                nodeStack.push(node.left);
                sumStack.push(remainingSum - node.val);
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(node.left.val);
                pathStack.push(newPath);
            }
        }
        
        return result;
    }
}

• 時間復雜度?：O(n)
• ?空間復雜度?：O(n)，需要存儲節點和路徑信息

BFS層序遍歷

使用隊列進行廣度優先搜索，同時記錄路徑和：

1. ?節點隊列?：存儲待處理的節點
2. ?路徑隊列?：存儲從根節點到當前節點的路徑
3. ?和隊列?：存儲從根節點到當前節點的路徑和

public class Solution {
    public List<List<Integer>> FindPath(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<List<Integer>> pathQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();
        
        nodeQueue.offer(root);
        pathQueue.offer(new ArrayList<>(Arrays.asList(root.val)));
        sumQueue.offer(root.val);
        
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            List<Integer> currentPath = pathQueue.poll();
            int currentSum = sumQueue.poll();
            
            // 檢查是否為葉子節點且路徑和等于目標值
            if (node.left == null && node.right == null && currentSum == targetSum) {
                result.add(new ArrayList<>(currentPath));
            }
            
            if (node.left != null) {
                nodeQueue.offer(node.left);
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(node.left.val);
                pathQueue.offer(newPath);
                sumQueue.offer(currentSum + node.left.val);
            }
            
            if (node.right != null) {
                nodeQueue.offer(node.right);
                List<Integer> newPath = new ArrayList<>(currentPath);
                newPath.add(node.right.val);
                pathQueue.offer(newPath);
                sumQueue.offer(currentSum + node.right.val);
            }
        }
        
        return result;
    }
}

• 時間復雜度?：O(n)
• ?空間復雜度?：O(n)，隊列存儲節點的空間