- 浏览: 18992 次
- 性别:
- 来自: 北京
文章分类
最新评论
题目描述
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.
解题思路
本题采用的总体思想是深度优先遍历。但是对深度优先遍历进行了变化,首先处理了空树的问题;其次因为要每次使用到所有祖先的和值,采用了减法的策略。
自己的代码
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.
解题思路
本题采用的总体思想是深度优先遍历。但是对深度优先遍历进行了变化,首先处理了空树的问题;其次因为要每次使用到所有祖先的和值,采用了减法的策略。
自己的代码
package leetcode; /*public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }*/ public class PathSum { public boolean hasPathSum(TreeNode root, int sum) { //处理空树的情况 if(root == null) return false; else{ sum = sum - root.val; if(root.left == null && root.right == null && sum == 0) return true; else { if(root.left != null){ if(hasPathSum(root.left, sum)) return true; } if(root.right != null){ if(hasPathSum(root.right, sum)) return true; } } } return false; } public static void main(String[] args) { TreeNode node1 = new TreeNode(5); TreeNode node2 = new TreeNode(4); TreeNode node3 = new TreeNode(8); TreeNode node4 = new TreeNode(11); TreeNode node5 = new TreeNode(13); TreeNode node6 = new TreeNode(4); TreeNode node7 = new TreeNode(7); TreeNode node8 = new TreeNode(2); TreeNode node9 = new TreeNode(1); node1.left = node2; node1.right = node3; node2.left = node4; node3.left = node5; node3.right = node6; node4.left = node7; node4.right = node8; node6.right = node9; /*node9.left = node8;*/ int sum = 22; //int sum = 10000; /*int sum = 1;*/ PathSum ps = new PathSum(); System.out.println(ps.hasPathSum(node1, sum)); //System.out.println(ps.hasPathSum(node9, sum)); } }
发表评论
-
Java中String与StringBuffer的区别
2014-10-29 21:07 297String和StringBuffer的区别,网上资料可以说 ... -
String to Integer (atoi)
2014-10-29 17:13 396题目描述 Implement atoi to convert ... -
Implement strStr()
2014-10-28 15:17 282题目描述 Implement strStr(). Retu ... -
Valid Palindrome
2014-10-23 10:32 418题目描述 Given a string, determine ... -
ZigZag Conversion
2014-10-22 19:51 340题目描述 The string "PAYPALIS ... -
Add Binary
2014-10-22 19:43 300题目描述 Given two binary strings, ... -
Longest Common Prefix
2014-10-22 19:44 326题目描述 Write a function to find t ... -
Count and Say
2014-10-22 19:44 345题目描述 The count-and-say sequence ... -
Valid Sudoku
2014-10-21 10:22 352题目描述 Determine if a Sudoku is v ... -
Valid Parentheses
2014-10-21 09:41 321题目描述 Given a string containing ... -
Palindrome Number
2014-10-21 09:41 343题目描述 Determine whether an integ ... -
Length of Last Word
2014-10-21 09:41 354题目描述 Given a string s consists ... -
Minimum Depth of Binary Tree
2014-10-21 09:41 306题目描述 Given a binary tree, find ... -
Remove Nth Node From End of List
2014-10-20 16:36 255题目描述 Given a linked list, remov ... -
Binary Tree Level Order Traversal II
2014-10-20 11:17 230题目描述 Given a binary tree, retur ... -
Binary Tree Level Order Traversal
2014-10-20 11:03 289题目描述 Given a binary tree, retur ... -
Pascal's Triangle II
2014-10-20 10:07 254题目描述 Given an index k, return t ... -
Pascal's Triangle
2014-10-19 12:24 316题目描述 Given numRows, generate th ... -
Plus One
2014-10-19 11:51 334题目描述 Given a non-negative numbe ... -
Merge Sorted Array
2014-10-18 10:45 396题目描述 Given two sorted integer a ...
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
113. Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree...
Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段树 Range Sum Query - Mutable 排序 插入排序 Insertion Sort List 归并排序 Merge ...
//将每一种可能性都放入set中,并依次与sum对比public int pathSum(TreeNode root, int mySum){//1.递归出口/
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 ...Sum ...Sum ...Sum ...Path Sum 73
命令行工具. 计算SHA1SUM,生成SHA1SUM文件.校验SHA1SUM文件. 如果安装了GnuPG,并在PATH中,对SHA1SUM进行明文签名(生成SHA1SUM.asc)或对其验证.
命令行工具. 计算SHA1SUM,生成SHA1SUM文件.校验SHA1SUM文件. 如果安装了GnuPG,并在PATH中,对SHA1SUM进行明文签名(生成SHA1SUM.asc)或对其验证. 修正对一些SHA1SUM.asc不能识别的bug
Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-...
leetcode叫数 Leetcode_JS leetcode编程题,javascript版本 ##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只需要遍历一遍...Sum 这道题是关于二叉树的题,递归思路,也就是DFS的思路。 这里递归
Path Sum 2017/03/09 70.Climbing Stairs, 198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, ...
第 338 章力码解决方案 问题编号 标题 困难 C Java Ruby 338 中等的 [✓](/src/338 计数位/solution.c) 104 简单的 [✓](/src/104 二叉树的最大深度/solution.c) ...Path Sum II/solution.java) 258 简单的 [✓](/
路径和解决leet码问题的方法,以查找树节点总和中是否存在给定的数字一个简单... 运行时间:4毫秒,比Path Sum的C ++在线提交的99.88%快。 内存使用:21.3 MB,少于Path Sum的C ++在线提交的96.61%。 德拉吉·吉达尔
算法命令行界面设置样板来解决问题。 要使用CLI,请执行以下步骤cd bin/npm link用法al new [name] [arguments] 示例1... 示例2:带有参数al new path - sum node sum 输出var pathSum = function ( node , sum ) { } ;
leetcode 树节点二叉树最大路径和 ...max_sum = Integer . MIN_VALUE ; public int max_gain ( TreeNode node ) { if (node == null ) return 0 ; // max sum on the left and right sub-trees of node int lef
多线程 leetcode 前言 每天刷点leetcode,基于java语言...Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
linux下使用md5sum递归生成整个目录的md5 今天要用md5sum操作目录,递归生成目录下所有文件的md5值,结果发现它不支持递归操作于是写了个php脚本处理下 代码: <?php $path ='/data/www/bbs/source'; $...
hm.put("sum",new Double(sum_dingdan)); }catch (Exception e){ System.out.println(e.getMessage()); bl=false; //System.out.println("false"); } return hm; } public void setPath(String...
训练模型:python3 ./run_seq2seq.py --model_name_or_path t5-base --do_train --do_eval -任务总结--train_file data / training_data.csv --validation_file data / testing_data.csv --output_dir ./tmp/tst-...
#!/usr/bin/ruby -w # require 'digest/md5' ...def dir_md5sum(path) md5s=Array.new if File.directory?(path) Dir.new(path).each do |file| next if file =~ /^\.+$/ file=#{path}/#{file}