Path Sum
发布时间:2020-12-14 04:30:03 所属栏目:大数据 来源:网络整理
导读: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. Note:?A leaf is a node with no children. Example: Given the below binary tree and? sum = 22
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. Note:?A leaf is a node with no children. Example: Given the below binary tree and? 5 / 4 8 / / 11 13 4 / 7 2 1 return true,as there exist a root-to-leaf path? Approach #1: 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; if (root->val == sum && root->right == NULL && root->left == NULL) return true; return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val); } };
Approach #2: Java. /** * Definition for a binary tree node. * public 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.val == sum && root.right == null && root.left == null) return true; return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } }
Approach #3: 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 root == None: return False if root.val == sum and root.left == None and root.right == None: return True return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |