【题目】
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 andsum
= 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path5->4->11->2
which sum is 22.
【分析】
题目要求是从根节点到叶子节点的一条路径。刚开始没看清楚,还以为随意路径。
题目只要求返回true或者false,因此没有必要记录路径。
【代码】
/*********************************
* 日期:2015-01-01
* 作者:SJF0115
* 题目: 112.Path Sum
* 来源:https://oj.leetcode.com/problems/path-sum/
* 结果:AC
* 来源:LeetCode
* 博客:
* 时间复杂度:O(n)
* 空间复杂度:O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 二叉树节点
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
// 找到一条从根节点到叶子节点的路径
if(root->left == NULL && root->right == NULL){
return sum == root->val;
}//if
// 左子树
bool left = hasPathSum(root->left,sum - root->val);
// 右子树
bool right = hasPathSum(root->right,sum - root->val);
return left || right;
}
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
int len = num.size();
if(len == 0){
return NULL;
}//if
queue<TreeNode*> queue;
int index = 0;
// 创建根节点
TreeNode *root = new TreeNode(num[index++]);
// 入队列
queue.push(root);
TreeNode *p = NULL;
while(!queue.empty() && index < len){
// 出队列
p = queue.front();
queue.pop();
// 左节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *leftNode = new TreeNode(num[index]);
p->left = leftNode;
queue.push(leftNode);
}
index++;
// 右节点
if(index < len && num[index] != -1){
// 如果不空创建一个节点
TreeNode *rightNode = new TreeNode(num[index]);
p->right = rightNode;
queue.push(rightNode);
}
index++;
}//while
return root;
}
int main() {
Solution solution;
// -1代表NULL
vector<int> num = {5,4,8,11,-1,13,4,7,2,-1,-1,-1,1};
TreeNode* root = CreateTreeByLevel(num);
cout<<solution.hasPathSum(root,22)<<endl;
}
分享到:
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
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...
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 and sum = 22, ...
129. Sum Root to Leaf Numbers Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents ...
Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window ...
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii ...112.path-sum (路径总和) 116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Sum ...Sum ...Sum ...Path Sum 73
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
leetcode叫数 Leetcode_JS leetcode编程题,javascript版本 ##NO.35 Search Insert Position 这道题非常简单,数组是有序数组,只...##NO.112 Path Sum 这道题是关于二叉树的题,递归思路,也就是DFS的思路。 这里递归
//将每一种可能性都放入set中,并依次与sum对比public int pathSum(TreeNode root, int mySum){//1.递归出口/
1、two-sum 能同时获取元素和index的方法是使用enumerate() 思路:从第一个元素开始,遍历,求每个位置上的差值保存到dict中,如果在接下来的元素在dict中出现,返回下标。。。真牛逼! 7、Reverse integer 字符串...
颜色分类leetcode 磁盘故障预测 只针对阿里巴巴AIOps岗位面试的编码测试 扫描当前目录下的所有CSV文件 import pandas as pd import glob , os , sys input_path = './' output_fiel = 'pandas_union_concat.csv' all...
多线程 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
进阶班七八节作业:矩阵的最小路径和:https://leetcode.com/problems/minimum-path-sum/description/最长递
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-...
$ cd /path/to/leetcode/c/ # /path/to/leetcode/cpp/ $ mkdir build $ cd build $ cmake .. $ cd .. CMake将自动生成buildsystem文件并下载 。 注意:添加新的单元测试后,请务必重新加载CMake。 要构建,请使用--...
leetcode 做题笔记 按照知识点分类 链表 链表反转 分治: 回溯/递归 全排列问题,用visited变量; 组合问题,用start变量。 其它 动态规划 区间型 [从左上角到右下角] [子序列/子串:公共长度问题,都是DP,只有一个...
leetcode 2 解决 Leetcode ...two-sum.py -t "[1,2]\n3" 提交问题: leetup submit two-sum.py 列表/显示问题: leetup list 按关键字搜索: leetup list 查询简单: leetup list -qe 按 ID、标题、难度l
算法命令行界面设置样板来解决问题。 要使用CLI,请执行以下步骤cd bin/npm link用法al new [name] [arguments] 示例1... 示例2:带有参数al new path - sum node sum 输出var pathSum = function ( node , sum ) { } ;