[LeetCode] 112. Path Sum 路径和

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 112. Path Sum 路径和,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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.html

For example:
Given the below binary tree and sum = 22,java

              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.node

给定一个二叉树和一个sum,问是否有一个从根到叶节点的路径,使得路径上全部的值加起来等于给定的sum。python

解法:最基本的深度优先搜索DFS(Depth-First Search),从根节点出发,搜索每个到叶节点的路径,而后判断和是否为sum。spa

Java:code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode (int x) { val = x; } 

}

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null & root.right == null & sum == root.val) return true;
        
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);   
    
    }    
  
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.right = new TreeNode(2);
        Solution sol = new Solution();
        System.out.println(sol.hasPathSum(root, 22));
    }
}  

Python:htm

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
class Solution:
    # @param root, a tree node
    # @param sum, an integer
    # @return a boolean
    def hasPathSum(self, root, sum):
        if root is None:
            return False
        
        if root.left is None and root.right is None and root.val == sum:
            return True
        
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

C++:blog

/**
 * Definition for binary tree
 * 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) {
        if (root == NULL) return false;
        if (root->left == NULL && root->right == NULL && root->val == sum ) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

  

相似题目:get

[LeetCode] 257. Binary Tree Paths 二叉树路径it

[LeetCode] 113. Path Sum II 路径和 II

[LeetCode] 437. Path Sum III 路径和 III