leetcode -day17 Path Sum I II & Flatten Binary Tree to Linked List & Minimum Depth of Binary Tree
1、
Path Sum
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.
分析，此题比較简单，採用深度优先策略。
代码例如以下：
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
hasPath = false;
if(root){
int tempSum = 0;
pathSumCore(root,tempSum,sum);
}
return hasPath;
}
void pathSumCore(TreeNode *root,int tempSum, int sum){
if(hasPath){
return;
}
tempSum += root->val;
if(!root->left&&!root->right){
if(tempSum == sum){
hasPath = true;
}
return;
}
if(root->left){
pathSumCore(root->left,tempSum,sum);
}
if(root->right){
pathSumCore(root->right,tempSum,sum);
}
}
bool hasPath;
};
2、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.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
分析：此题也非常easy。常见题，跟上述不同的是保存路径。
代码：
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
if(root){
int tempSum = 0;
vector<int> path;
pathSumCore(root,path,tempSum,sum);
}
return pathVec;
}
void pathSumCore(TreeNode* root,vector<int> path,int tempSum,int sum){
tempSum += root->val;
path.push_back(root->val);
if(!root->left && !root->right){
if(tempSum == sum){
pathVec.push_back(path);
}
return;
}
if(root->left){
pathSumCore(root->left,path,tempSum,sum);
}
if(root->right){
pathSumCore(root->right,path,tempSum,sum);
}
}
vector<vector<int> > pathVec;
};
3、Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
分析：上述提示能够看出，相当于二叉树的先序遍历，对每个结点，先訪问根结点，再先序遍历左子树。串在根结点的右孩子上，再先序遍历原右子树，继续串在右孩子上。
代码例如以下：
class Solution {
public:
void flatten(TreeNode *root) {
if(root){
preOrder(root);
}
}
TreeNode *preOrder(TreeNode *root){
if(!root->left && !root->right){
return root;
}
TreeNode *lastNode = NULL;
TreeNode *rightNode = root->right;
//TreeNode *leftNode = root->left;
if(root->left){
root->right = root->left;
lastNode = preOrder(root->left);
root->left = NULL;
lastNode->right = rightNode;
}
if(rightNode){
lastNode = preOrder(rightNode);
}
return lastNode;
}
};
4、Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析：此题非常easy，递归。
class Solution {
public:
int minDepth(TreeNode *root) {
if(!root){
return 0;
}
n_minDepth = INT_MAX;
int tempDepth = 0;
minDepthCore(root,tempDepth);
return n_minDepth;
}
void minDepthCore(TreeNode *root,int tempDepth){
++tempDepth;
if(tempDepth >= n_minDepth){
return;
}
if(!root->left && !root->right){
if(tempDepth < n_minDepth){
n_minDepth = tempDepth;
}
return;
}
if(root->left){
minDepthCore(root->left,tempDepth);
}
if(root->right){
minDepthCore(root->right,tempDepth);
}
}
int n_minDepth;
};
最新文章
- 『.NET Core CLI工具文档』（十二）dotnet-pack
- 翻译：打造Edge渲染内核的浏览器
- axis 理解
- 为vs2012添加背景和皮肤
- Oracle Statspack报告中各项指标含义详解~~学习性能必看！！！
- Dynamics CRM 开发模板使用手册（插件开发）
- flask中下载服务器上特定路径的文件
- 从源码浅析Java中的Lock和AbstractQueuedSynchronizer
- GEFGWT的HelloWorld
- 探索Windows命令行系列(4)：通过命令操作文件和文件夹
- 【原创】深入理解c++的右值引用
- appium-基本操作的再次封装（加上文件路径、log、截图、异常处理）
- 【转】Max2013脚本工具的乱码问题
- JQuery操作元素的属性与样式及位置
- day32(表单校验js和jquery表单校验)
- maven工程聚合和继承的意义
- WebForm 【简单控件】【表单元素】
- 005-Go 操作PostgreSQL数据库
- IP地址格式转换（htonl、ntohl；inet_addr、inet_ntoa）
- Spring 利用PropertyPlaceholderConfigurer占位符