劍指 Offer 34. 二叉樹中和為某一值的路徑

一、題目

列印出二叉樹中節點值的和為輸入整數的所有路徑（從根節點一直到葉子節點的路徑）

輸入：

給定如下二叉樹，以及目标和 target = 22

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
           

輸出：

[
   [5,4,11,2],
   [5,8,4,5]
]
           

二、解法

由根節點出發，首先想到先序周遊的思路

2.1 回溯

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
      if (root == nullptr) {
        return {};
      }
      vector<int> path;
      vector<vector<int>> ans;
      int currentSum = 0;
      FindPath(root, target, path, currentSum, ans);
      return ans;
    }

    void FindPath(TreeNode* root, int target, vector<int>& path, int currentSum, vector<vector<int>>& ans) {
      // 先序周遊
      currentSum += root->val;  // 更新目前路徑
      path.push_back(root->val);
      // 如果是葉子節點，并且路徑上的節點的和等于輸入的值，則列印這條路徑
      bool isLeaf = root->left == nullptr && root->right == nullptr;
      if (currentSum == target && isLeaf) {
        ans.push_back(path);
      }
      // 若不是葉子節點，則周遊它的子節點
      if (root->left != nullptr) {
        FindPath(root->left, target, path, currentSum, ans);
      }
      if (root->right != nullptr) {
        FindPath(root->right, target, path, currentSum, ans);
      }
      // 在傳回父節點之前，在路徑上删除目前節點
      path.pop_back();  // 回溯
    }
};
           

複雜度分析

• 時間複雜度：O(N)，N為二叉樹的節點數，需要周遊所有節點
• 空間複雜度：O(N)，最差情況下即樹退化成連結清單，path存儲所有樹節點，使用O(N)額外空間