【LeetCode】113. Path Sum II 基于Java和C++的解法及分析

柔光的暖阳◎ 2022-08-22 01:13 28阅读 0赞

### 113. Path Sum II   Total Accepted: 80509 Total Submissions: 284188 Difficulty: Medium ###

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

【分析】

此题和【LeetCode】112题基本方法一样，但要复杂一些。由于合法路径要求为根节点到叶子节点（root to leaf），搜索算法我们采用DFS（深度优先搜索），搜索路径采用中序遍历（左-根-右），由于满足要求的路径可能非唯一，搜索中需要注意“回溯”。

结合题目中的例子，简述思路如下：

1.采用中序遍历，则从根节点5起，首先搜索左孩子节点，一直到达叶子节点为止，第一条合法路径为：5-4-11-7， 检验路径和是否满足约束条件（sum==22）；

2.若满足则将路径保存起来；

3.然后，当前路径尾端数据弹出，剩余5-4-11，返回，相当于回到根节点11；

4.继续搜索右孩子结点，2为叶子节点，因而合法路径为：5-4-11-2，检验其是否满足约束条件；

5.....

【注意事项】 执行当前路径尾端数据弹出的操作有两个位置：

1.遍历至叶子节点，形成合法路径，在检验路径是否满足约束条件并保存后，弹出末端数据，返回，如此便可回到最近的根节点，然后继续搜索该根节点的子节点；

2.某一根节点的左右子节点遍历完毕，如根节点11的子节点7和2遍历完毕，须返回上一层，这时候需要弹出根节点11，则当前搜索路径变为：5-4；根节点4没有右叶子节点，弹出4，返回上一层5,根节点5有右子节点，继续中序遍历...

【基于C++的解法】

/**
     * 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:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            
            vector<vector<int>> result;//存放满足要求的路径
            vector<int> cur;//当前路径
            if(root==NULL)return result;
            
            DFS(result,cur,root,sum);//深度搜索
            return result;
        }
        
        void DFS(vector<vector<int>> &result,vector<int> &cur,TreeNode* root,int sum)
        {
            if(root==NULL)return;
            if(root->left==NULL&&root->right==NULL)//到达叶子节点，形成合法路径，这时候再对路径进行验证
            {
                cur.push_back(root->val);//叶子节点纳入当前路径
                if(sumOfPath(cur)==sum)//检验路径是否满足约束
                result.push_back(cur);
                
                cur.pop_back();//弹出当前路径末端数据并返回
                return;
            }
            else
            {
                cur.push_back(root->val);//中序遍历的构架
                DFS(result,cur,root->left,sum);
                DFS(result,cur,root->right,sum);
                cur.pop_back();//某一根节点的子节点搜索完毕，末端数据弹出，返回上一层
            }
        
        }
        
        int sumOfPath(vector<int> &dataSet)//求取路径和
        {
            int sum=0;
            for(int i=0;i<dataSet.size();i++)
            {
                sum+=dataSet[i];
            }
            return sum;
        }
    };

运行结果：

![Center][]

【基于Java的解法】关于Java解法的细节知识，请见我的另一篇博客。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public List<List<Integer>> pathSum(TreeNode root, int sum) 
        {
    	   List<List<Integer>> result=new ArrayList<List<Integer>>();//List接口变量用的ArrayList类对象实例化
    	   List<Integer> temp=new ArrayList<Integer>();
    	   
    	   if(root==null)return result;
    	   DFS(result,temp,root,sum);
    	   return result;
        }
        
        void DFS(List<List<Integer>> result,List<Integer> temp,TreeNode root,int sum)
        {
    	   if(root==null)return;
    	   if(root.left==null&&root.right==null)
    	   {
    		   temp.add(root.val);
    		   if(sumOfPath(temp)==sum)
    			   result.add(new ArrayList(temp));//一定要注意
    		   temp.remove(temp.size()-1);
    		   return;
    	   }
    	   else
    	   {
    		   temp.add(root.val);
    		   DFS(result,temp,root.left,sum);
    		   DFS(result,temp,root.right,sum);
    		   temp.remove(temp.size()-1);
    	   }
       }
       
       int sumOfPath(List<Integer> temp)
       {
    	   int sum=0;
    	   for(int i=0;i<temp.size();i++)
    	   {
    		   sum+=temp.get(i);
    	   }
    	   return sum;
       }
    }

运行结果：  
![Center 1][]

[Center]: /images/20220724/3ba0ccedbf5f42118a49ccce2023c311.png
[Center 1]: /images/20220724/2c31191530414da4afea54d7874db15a.png