欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer之“二叉树中和为某一值的路径”

程序员文章站 2022-06-09 20:28:01
...

刷题笔记:剑指offer之“二叉树中和为某一值的路径”

序言:马上就要秋招了,开始意识到自己变成和算法能力不足,所以这几天开始准备刷题,并把解题思路记录下来。主要讲解:题目介绍、问题分析和算法详解。(实现语言为C++)

编程代码以上传至:https://github.com/walman6/code_programming有兴趣的童鞋可以查看。


题目

题目描述:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

问题分析

这个问题本质是对树的遍历方式进行考虑,着重考察“深度优先遍历”的方法。从根节点出发找到满足节点之和为expectNumber的路径(注意:从根节点出发找到满足要求的路径。)

剑指offer之“二叉树中和为某一值的路径”

算法详解

先给出代码:

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    /*
        深度优先遍历节点信息
    */
    void DFSFind(TreeNode* root,int expectNumber, vector<vector<int> > &findPath, vector<int> &trace){
        trace.push_back(root->val);
        if(expectNumber == root->val && root->left == NULL && root->right == NULL){
            findPath.push_back(trace);
        }
        if(root->left != NULL){
            DFSFind(root->left, expectNumber-root->val, findPath, trace);
        }
        if(root->right != NULL){
            DFSFind(root->right, expectNumber-root->val, findPath, trace);
        }
        trace.pop_back();
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > findPath;
        vector<int> trace;
        if(root != NULL) DFSFind(root, expectNumber, findPath, trace);
        return findPath;
    }
};

代码中: FindPath函数为系统给定接口,期初我考虑在给定函数中使用递归的方法结果异常返回NULL,但是函数返回值不能给定NULL或者vector<vector<int> >()。最后意识到可以自定义一个void function对于满足条件进行处理就能解决这个问题。考察DFS(深度优先遍历)代码编写,首先添加输入节点判断是否满足条件,如果满足进行路径添加,否则递归进行后续DFS过程。 在DFS后需要对节点弹出,便于后面其他路径判断。

思考:如果任意节点下满足路径节点之和为expectNumber的所有路径,且不包括叶子节点。

相关标签: 编程练习