[LeetCode] Path Sum 二叉树的路径和

[LeetCode] Path Sum 二叉树的路径和

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.

/// 112. Path Sum/// 时间复杂度: O(n), n为树的节点个数/// 空间复杂度: O(h), h为树的高度class Solution { // Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(root.left == null && root.right == null) return sum == root.val; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}

类似问题:

1. 404sum of left leaves

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。