leetcode 112. Path Sum DFS深度优先遍历-蒲公英云

leetcode 112. Path Sum DFS深度优先遍历

以你之姓@ 2022-06-08 03:17 310阅读 0赞

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

这道题考察的就是每一条路径的sum，找到target即可。

代码如下：

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<Integer> res=new ArrayList<Integer>();
    public boolean hasPathSum(TreeNode root, int sum) 
    {
        if(root==null)
            return false;
        else
            return bydfs(root,sum);
    }
    public boolean bydfs(TreeNode root, int sum)
    {
        if(root!=null)
        {
            if(root.left==null && root.right==null)
                return root.val==sum;
            boolean left  = bydfs(root.left, sum-root.val);
            boolean right = bydfs(root.right, sum-root.val);
            return left || right;
        }else 
            return false;
    }
}

下面是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:
    bool hasPathSum(TreeNode* root, int sum) 
    {
        return bydfs(root, 0, sum);
    }
    bool bydfs(TreeNode* root, int a, int sum)
    {
        if (root == NULL)
            return false;
        else
        {
            if (root->left == NULL && root->right == NULL)
            {
                if (a + root->val == sum)
                    return true;
                else
                    return false;
            }
            else
            {
                bool left = bydfs(root->left, a + root->val, sum);
                bool right = bydfs(root->right, a + root->val, sum);
                return left || right;
            }
        }
    }
};