一 唠嗑
我又拖更了,我出来挨打
因为最近校招快开始了,为了帮助更多的同学,我进度拉快一点,递归回溯问题,到N皇后,已经比较难了,当然我这还有难题,以后慢慢更,这个程度已经可以了
本来递归&回溯之后,我想更贪心算法的,但是我看了看贪心的题都比较简单,想了想还是先把重要的二叉树和图在前面先讲完,再更比较简单的贪心,毕竟有参加提前批的同学嘛~
什么,你问我这周会不会还拖更?
二 上题!
建议大家复习一下二叉树的基础知识,比如常见的三种遍历,前,中,后序遍历(递归),以及层次遍历(利用队列),我就不多赘述了~
Q:给定一个二叉树和整数sum,返回所有,根节点到叶节点的路径中,和为sum的路径。
举例:网上找的图,给定sum = 22
则需要返回 [[5, 4, 11, 2], [5, 8, 4, 5]]
三 冷静分析
首先我们要知道,二叉树的题,我们首先要想到用递归&回溯的思想,如果不行,或者不允许使用,再想其他的方法~
其次二叉树的遍历过程中,存储节点,或者节点的值,和栈&队列又有千丝万缕的联系,结合使用,就是二叉树算法的精髓了。
我们可以这样处理逻辑:
1.从根节点,深搜二叉树,将节点值存储在路径栈path中;
2.遍历到叶子节点时,判断当前路径和是否为sum,若是,将该路径,添加进二维数组result中;
3.出每层的递归后,将该节点从路径栈中弹出,并将路径和pathValue减去该节点的值,来实现向上回溯。
四 完整代码及注释
//
// Created by renyi on 2019-07-03.
//
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode{//二叉树的每个节点的数据结构
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : value(v), left(NULL), right(NULL) {}
};
void preOrder(TreeNode* root, int &pathValue, int sum, vector<int> &path, vector<vector<int>> &result){
if (!root){
return;
}
pathValue += root->value;//遍历一个节点就更新一下路径值
path.push_back(root->value);//将节点值push进路径栈path
if (!root->left && !root->right && pathValue == sum){
result.push_back(path);
}
preOrder(root->left, pathValue, sum, path, result);
preOrder(root->right, pathValue, sum, path, result);
pathValue -= root->value;//这里出递归,向上回溯,所以减去节点值
path.pop_back();//并将当前节点弹出路径栈path
}
vector<vector<int>> pathSum(TreeNode* root, int sum){
vector<vector<int>> result;//初始化二维数组result,存储最后结果
vector<int> path;//路径栈path
int pathValue = 0;
preOrder(root, pathValue, sum, path, result);
return result;
}
int main(){
TreeNode a(5);//建立配图的二叉树
TreeNode b(4);
TreeNode c(8);
TreeNode d(11);
TreeNode e(13);
TreeNode f(4);
TreeNode g(7);
TreeNode h(2);
TreeNode i(5);
TreeNode j(1);
a.left = &b;
a.right = &c;
b.left = &d;
c.left = &e;
c.right = &f;
d.left = &g;
d.right = &h;
f.left = &i;
f.right = &j;
vector<vector<int>> result = pathSum(&a, 22);
for (int m = 0; m < result.size(); m++) {
for (int n = 0; n < result[m].size(); n++) {
printf("[%d]", result[m][n]);
}
printf("\n");
}
return 0;
}
运行结果