[数据结构与算法] 【算法】JZ34 二叉树中和为某一值的路径(二)[回溯法]

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法】JZ34 二叉树中和为某一值的路径(二)[回溯法] -> 正文阅读

[数据结构与算法]【算法】JZ34 二叉树中和为某一值的路径(二)[回溯法]

题目链接

在这里插入图片描述

回溯法

定义结果集合待选结果集，分别存放最后结果和本次结果。
分为以下四步：
1、先把当前值添加进待选结果集
2、判断当前结果是否满足条件
3、深度优先遍历
4、回退

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void _FindPath(TreeNode* root, int expectNumber, vector<vector<int>>& vv, vector<int>& v)
    {
        if(root == nullptr)
            return;
        // 添加待选值
        v.push_back(root->val);
        expectNumber -= root->val;
        // 判断现有结果是否满足条件，剪枝
        if(0 == expectNumber && root->left == nullptr && root->right == nullptr)
            vv.push_back(v);
        // DFS
        _FindPath(root->left, expectNumber, vv, v);
        _FindPath(root->right, expectNumber, vv, v);
        // 回退
        v.pop_back();
    }
        
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> vv;  // 结果集
        if(nullptr == root)
            return vv;
        vector<int> v; // 保存每一次结果
        _FindPath(root, expectNumber, vv, v);
        return vv;
    }
};