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

以你之姓@ 2022-06-08 03:17 150阅读 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;
                }
            }
        }
    };