leetcode 113. Path Sum II DFS深度优先遍历

超、凢脫俗 2022-06-08 04:15 194阅读 0赞

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深度优先遍历，不过这里要求**到叶子节点**，所以这个和二叉树的遍历稍有不同，直接上代码吧！

建议和[leetcode 437. Path Sum III 深度优先遍历DFS][leetcode 437. Path Sum III _DFS] 和 [leetcode 112. Path Sum DFS深度优先遍历][leetcode 112. Path Sum DFS] 一起学习

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*class TreeNode 
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    public class Solution 
    {
        List<List<Integer>> res=new ArrayList<>();
        public List<List<Integer>> pathSum(TreeNode root, int sum) 
        {
            if(root==null)
                return res;
            List<Integer> one=new ArrayList<>();
            byRecursion(root,one,sum,0);
            return res;
        }
    
        public void byRecursion(TreeNode root,List<Integer> one,int target,int sum) 
        {
            if(root==null)
                return;
            else
            {
                //左右的子节点都为null的时候，就表明走到了叶节点了
                if(root.left==null && root.right==null)
                {
                    one.add(root.val);              
                    if(sum+root.val==target)
                    {
                        List<Integer> t=new ArrayList<>(one);
                        res.add(t);
                    }
                    one.remove(one.size()-1);
                    return;
                }
                //左子树遍历
                if(root.left!=null)
                {
                    one.add(root.val);
                    byRecursion(root.left,one,target,sum+root.val);
                    one.remove(one.size()-1);
                }
                //右子树遍历
                if(root.right!=null)
                {
                    one.add(root.val);
                    byRecursion(root.right,one,target,sum+root.val);
                    one.remove(one.size()-1);
                }
            }
        }
    }

下面是C++的做法，就是一个DFS深度优先遍历的做法

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        vector<vector<int>> res;
        vector<vector<int>> pathSum(TreeNode* root, int sum)
        {
            vector<int> one;
            bydfs(root,one, 0, sum);
            return res;
        }
    
        void bydfs(TreeNode* root, vector<int> one, int a, int sum)
        {
            if (root == NULL)
                return ;
            else
            {
                one.push_back(root->val);
                if (root->left == NULL && root->right == NULL)
                {
                    if (a + root->val == sum)
                        res.push_back(one);
                    else
                        return;
                }
                else
                {
                    bydfs(root->left,one, a + root->val, sum);
                    bydfs(root->right,one, a + root->val, sum);
                }
                one.erase(one.end() - 1);
            }
        }
    };

[leetcode 437. Path Sum III _DFS]: http://blog.csdn.net/JackZhang_123/article/details/78752985
[leetcode 112. Path Sum DFS]: http://blog.csdn.net/jackzhang_123/article/details/77962275