`
bcyy
  • 浏览: 1809352 次
文章分类
社区版块
存档分类
最新评论

Path Sum -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/path-sum/
这道题是树操作的题目,判断是否从根到叶子的路径和跟给定sum相同的。还是用常规的递归方法来做,递归条件是看左子树或者右子树有没有满足条件的路径,也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的,则返回false,如果是叶子,那么如果剩余的sum等于当前叶子的值,则找到满足条件的路径,返回true。算法的复杂度是输的遍历,时间复杂度是O(n),空间复杂度是O(logn)。代码如下:
public boolean 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中出现的频率很高,不过方法都很接近,掌握了就都差不多。这类求解树的路径的题目是一种常见题型,类似的还有Binary Tree Maximum Path Sum,那道题更加复杂一些,路径可以起始和结束于任何结点(把二叉树看成无向图),有兴趣的朋友可以看看哈。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics