Try   HackMD

【LeetCode】 113. Path Sum II

Description

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

給你一棵二元樹和一個總和值,找到從樹根到樹葉的路徑中,所有節點加總等於給予的總和值的路徑。

提示:一個樹葉就是沒有小孩的節點。

Example:

Example:

Given the below binary tree and sum = 22,

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

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

Solution

  • DFS跑所有路線,跑到樹根時去判斷總和有沒有相等,有的話就加到答案中。
  • 如果確定二元樹的值都是非負數,可以進行剪枝加速,不過這邊我沒有去測試。

Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void DFS(vector<vector<int>>& ans, vector<int> path, TreeNode* node, int sum, int target) { if(!node) { return; } path.push_back(node->val); sum+=node->val; if(!node->left && !node->right) { if(sum == target) ans.push_back(path); return; } DFS(ans,path,node->left,sum,target); DFS(ans,path,node->right,sum,target); } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> ans; DFS(ans,vector<int>(0,0),root,0,sum); return ans; } };
tags: LeetCode C++