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

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，问是否有一个从根到叶节点的路径，使得路径上所有的值加起来等于给定的sum。

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

Java:

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:

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++:

/**

 * 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);

    }

};

类似题目：

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

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

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

巴特西

[LeetCode] 112. Path Sum 路径和

最新文章

热门文章