Day18-二叉树-路径之和

一 唠嗑

我又拖更了,我出来挨打

因为最近校招快开始了,为了帮助更多的同学,我进度拉快一点,递归回溯问题,到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;
}

运行结果

原文发布于微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi)

原文发表时间:2019-07-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券