題目描述

257. 二叉樹的所有路徑

解題思路

1. 題意理解

   給定一棵二叉樹，要求返回所有從根節點到葉子節點的路徑，路徑以字符串形式表示，格式如 “1->2->5”。

2. 算法選擇：DFS + 回溯

   由于需要找出所有從根到葉子的路徑，自然想到使用深度優先遍歷（DFS）。

   同時，因為路徑是一個從根開始的逐步構建過程，我們需要在遞歸過程中記錄當前路徑，并在遞歸返回時撤銷（回溯）上一步的選擇。

3. 遞歸終止條件

   如果遇到了 null ，向上返回

   如果遇到了 葉子節點 ，說明得到了一條新的路徑，加入結果集，然后返回。

4. 路徑的記錄與處理

   我們使用一個數組 path 來記錄當前從根節點到當前節點的路徑。

   當遇到葉子節點（即 left == null && right == null）時，把 path 用 “->” 連接成字符串加入最終結果數組。

   注意：每次遞歸后需要 回溯（pop彈出） 上一個節點，確保路徑的正確性。

5. 邊界情況處理

   如果根節點為 null，直接返回空數組。

   如果樹中只有一個節點，也能正常處理為一個路徑。

更直觀的理解：
想象你正站在一棵樹的某個節點上，此時路徑數組（path）中保存的是從根節點到當前節點所經過的路徑。
接下來，你需要繼續從當前節點出發，分別向的左子樹和右子樹遞歸前進。
當你遇到空節點或葉子節點（即遞歸的終止條件）時，說明當前這條路徑已經走到盡頭，此時會開始從下往上返回，并在返回的過程中撤銷剛剛加入的路徑節點（這一步是“回溯”），以便嘗試其他分支的路徑。

完整代碼

遞歸寫法，也可以用迭代

var binaryTreePaths = function(root) {let res = [];let path = [];function dfs(node) {if (node === null) returnpath.push(node.val);// 如果是葉子節點，就把路徑加入結果if (!node.left && !node.right) {res.push(path.join('->'));return}// 繼續遞歸左右子樹dfs(node.left);dfs(node.right);// 回溯path.pop();}dfs(root);return res;
};

時間復雜度分析

• 遍歷了所有節點：O(N)，其中 N 是節點數。

• 每條路徑最長為樹高 H，每條路徑轉為字符串的時間是 O(H)，總共最多 N 個葉子節點。
  所以最壞情況總時間為：O(N * H)。