首页 > 代码库 > [leetcode]_Path Sum I && II

[leetcode]_Path Sum I && II

2024-07-06 04:42:30   224人阅读

都是考查DFS。经典回溯算法，问题在于我对该类型的代码不熟悉，目前以参考别人的代码，然后加上自己的实现为主，通过类似的题目加强理解。

 

一、给定一棵二叉树，判断是否存在从root到leaf的路径和等于给定值sum，存在返回true，否则返回false。

思路：DFS。

代码：

 1     private boolean ifExist = false;
 2     public boolean hasPathSum(TreeNode root, int sum) {
 3         dfs(root , sum , 0);
 4         return ifExist;
 5     }
 6     public void dfs(TreeNode node , int sum , int tempSum){
 7         if(node == null) return;
 8         
 9         tempSum += node.val;
10         if(node.left == null && node.right == null && tempSum == sum){
11             ifExist = true;
12             return;
13         }
14         dfs(node.left , sum , tempSum);
15         dfs(node.right , sum , tempSum);
16         
17     }

 

 网络上的DFS代码写的很流畅：参考一下，希望以后能写出这么流畅、舒服的代码。

 1     public boolean hasPathSum(TreeNode root, int sum) {
 2         if(root == null) return false;
 3         
 4         int leftSum = sum - root.val;
 5         if(leftSum == 0 && root.left == null && root.right == null) return true;
 6         
 7         boolean left = hasPathSum(root.left , leftSum);
 8         boolean right = hasPathSum(root.right , leftSum);
 9         return left || right;
10     }

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

二、题目：在上题的基础上，如存在路径，则返回具体路径。

代码：

 1 public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
 2         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 3         
 4         ArrayList<Integer> path = new ArrayList<Integer>();
 5         dfs(root , 0 , sum , path , result);
 6         return result;
 7     }
 8 
 9     public void dfs(TreeNode node , int tempSum , int sum , ArrayList<Integer> curPath , ArrayList<ArrayList<Integer>> result ){
10         if(node == null) return;
11         
12         tempSum = tempSum + node.val;
13         
14         if(node.left == null && node.right == null){
15             if(tempSum == sum){
16                 curPath.add(node.val);
17                 ArrayList<Integer> path = new ArrayList<Integer>(curPath); 
                   //用另一个list来转存一下，以便在后来对curPath的操作不会影响到已经add进result的数据。
18                 result.add(path);
19                 curPath.remove(curPath.size() - 1);
20                 //当前路径被记录后，记得删掉添加到list中的节点，回溯
21             }
22             return;
23         }
24         
25         curPath.add(node.val);
26         dfs(node.left , tempSum , sum , curPath , result);
27         dfs(node.right , tempSum , sum , curPath , result);
28         curPath.remove(curPath.size() - 1);
29         //该节点的左右节点都已经被访问过了，要删掉在list中该节点的记录，回溯
30     }

 

 DFS的代码还写的很生硬，需要多加练习。

 


联系
我们