112.Path Sum(Tree-Easy)

Jack_Cui

发布于 2018-01-08 15:12:55

6850

发布于 2018-01-08 15:12:55

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返回True，如果不等于sum返回False。

思路：遍历根结点到叶结点的每个结点的和即可。

Language ： python

最先想到以下方法，该方法遍历所有可能，然后返回最终的遍历结果。思路简单，但是缺点也明显，就是有多余的遍历。该方法不是找到满足要求的路径，立刻就返回，而是需要遍历所有的路径之后，再返回最终结果。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right and root.val == sum:
            return True
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

这种方法是基于上面算法的改进，找到满足要求的路径，立马返回结果，不再继续遍历，速度变快很多。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        elif not root.left and not root.right and root.val == sum:
            return True
        for child in (root.left, root.right):
            if child:
                if self.hasPathSum(child, sum - root.val):
                    return True
        return False

Language : cpp

对应上述方法的C++代码

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

LeetCode题目汇总： https://github.com/Jack-Cherish/LeetCode

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-07-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python