LeetCode OJ：Path Sum II（路径和II）

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

For 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]

]

求路径的和与某一特定的值时候对等即可，简单的dfs，代码如下：

 class Solution {

 public:

     vector<vector<int>> pathSum(TreeNode* root, int sum) {

         vector<int> res;

         dfs(root, res, sum);

         return ret;

     }

     void dfs(TreeNode * root, vector<int> res, int left)

     {

         if(!root) return;

         if(!root->left && !root->right && left == root->val){

             res.push_back(root->val);

             ret.push_back(res);

         }

         if(left <= root->val)

             return;

         else{

             res.push_back(root->val);

             if(root->left)

                 dfs(root->left, res, left -= root->val);

             if(root->right)

                 dfs(root->right, res, left -= root->val);

         }

     }

 private:

     vector<vector<int>> ret;

 };

java版本代码如下，方法相同，就是java的引用处理起来稍微麻烦点，递归尾部应该pop一下。

 public class Solution {

     public List<List<Integer>> pathSum(TreeNode root, int sum) {

         List<List<Integer>> ret = new ArrayList<List<Integer>>();

         Stack<Integer> tmp = new Stack<Integer>();

            dfs(ret, tmp, root, sum);

            return ret;

     }

     public void dfs(List<List<Integer>> ret, Stack<Integer> tmp, TreeNode root, int remain){

         if(root == null) return;

         tmp.push(root.val);

         if(root.left == null && root.right == null)

             if(remain == root.val)

                 ret.add((Stack<Integer>)tmp.clone());

         if(root.left != null) dfs(ret, tmp, root.left, remain - root.val);

         if(root.right != null) dfs(ret, tmp, root.right, remain - root.val);

         tmp.pop();

     }

 }

巴特西

LeetCode OJ：Path Sum II（路径和II）

最新文章

热门文章