二叉树中和为某一值的路径

亦凉 2023-03-14 05:26 10阅读 0赞

## 一、前言 ##

继续树相关的问题

## 二、题目 ##

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

## 三、思路 ##

用递归解决，简单直观。需要注意状态恢复。

在每次调用完递归之后，怎样恢复到当前结点状态，例如 A 中执完左结点搜索，准备进行右结点搜索，此时需要保证容器（用于记录路径）中记录的结点和左搜索时是一样的。有两种方法：

方法一，每次进行赋值即可。理解方便，但是会进行多次赋值操作

方法二，使用引用，递归函数自己赋值状态恢复，例如A，左结点调用完将容器恢复到使用前，流程看下图。理解复杂一下，效率较方法一要高一点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

##  ##

## 四、编码实现 ##

// FindPath.h
    
    #pragma once
    #include <vector>
    #include "ConstructTree.h"
    #include "Common.h"
    
    using namespace std;
    
    #define NAMESPACE_NAME_FINDPATH namespace NAME_FINDPATH {
    #define NAMESPACE_NAME_FINDPATHEND }
    // 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。、
    // 方法一
    template<class T = int>
    void FindPathEX(BinaryTreeNode<T> * pRoot, T sum, vector<vector<T>>& resultVect, vector<T> tempVect)
    {
    	if (pRoot == nullptr)
    	{
    		return;
    	}
    
    	tempVect.push_back(pRoot->m_nValue);
    	sum -= pRoot->m_nValue;
    	if (sum == 0 && pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr)
    	{
    		resultVect.push_back(tempVect);
    	}
    	else
    	{
    		FindPath(pRoot->m_pLeft, sum, resultVect, tempVect);
    		FindPath(pRoot->m_pRight, sum, resultVect, tempVect);
    	}
    
    	//tempVect.pop_back();
    }
    
    // 方法二
    template<class T = int>
    void FindPath(BinaryTreeNode<T> * pRoot, T sum, vector<vector<T>> & resultVect, vector<T>& tempVect)
    {
    	if (pRoot == nullptr)
    	{
    		return;
    	}
    
    	tempVect.push_back(pRoot->m_nValue);
    	sum -= pRoot->m_nValue;
    	if (sum == 0 && pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr)
    	{
    		resultVect.push_back(tempVect);
    	}
    	else
    	{
    		FindPath(pRoot->m_pLeft, sum, resultVect, tempVect);
    		FindPath(pRoot->m_pRight, sum, resultVect, tempVect);
    	}
    
    	tempVect.pop_back();
    }
    
    template<class T = int>
    void FindPath(BinaryTreeNode<T> * pRoot, T sum, vector<vector<T>> & resultVect)
    {
    	if (pRoot == nullptr)
    	{
    		return;
    	}
    
    	vector<T> tempVect;
    	FindPathEX(pRoot, sum, resultVect, tempVect);
    }
    
    
    NAMESPACE_NAME_FINDPATH
    
    //
    // 测试 用例 START
    template<class T>
    void test(const char* testName, BinaryTreeNode<T>* pRoot, T sum, vector<vector<T>>& resultVect, vector<vector<int>> expectVect)
    {
    	FindPath(pRoot, sum, resultVect);
    
    	bool ret = true;
    	if (resultVect.size() == expectVect.size())
    	{
    		for (size_t i = 0; i < resultVect.size(); i++)
    		{
    			if (resultVect[i] != expectVect[i])
    			{
    				ret = false;
    				break;
    			}
    		}
    	}
    	else
    	{
    		ret = false;
    	}
    
    	if (ret)
    	{
    		cout << testName << "solution passed." << endl;
    	}
    	else
    	{
    		cout << testName << "solution failed." << endl;
    	}
    }
    
    // 完全二叉树
    //              1
    //           /     \
    //          2       3  
    //         / \     / \
    //        4   5   6   7
    void Test1()
    {
    
    	const int length = 7;
    	int preorder[length] = { 1,2,4,5,3,6,7 };
    	int inorder[length] = { 4,2,5,1,6,3,7 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	vector<vector<int>> resultVect;
    	int sum = 8;
    
    	vector<vector<int>> expectVect;
    	vector<int> t1 = { 1,2,5 };
    	expectVect.push_back(t1);
    	test("Test1", pRoot, sum, resultVect, expectVect);
    }
    
    void Test2()
    {
    	const int length = 9;
    	int preorder[length] = { 3,1,4,7,5,6,2,8,4 };
    	int inorder[length] = { 7,4,1,5,6,3,8,2,4 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	vector<vector<int>> resultVect;
    	int sum = 15;
    	
    	vector<vector<int>> expectVect;
    	vector<int> t1 = { 3,1,4,7 };
    	expectVect.push_back(t1);
    	vector<int> t2 = { 3,1,5,6 };
    	expectVect.push_back(t2);
    
    	test("Test2", pRoot, sum, resultVect, expectVect);
    }
    // 测试 用例 END
    //
    NAMESPACE_NAME_FINDPATHEND
    
    void FindPath_Test()
    {
    	NAME_FINDPATH::Test1();
    	NAME_FINDPATH::Test2();
    }

**执行结果：**

![20200515235354453.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230312/784c0ae2bcaa4d6aaf3d32809c5d51cc.png
[20200515235354453.png]: /images/20230312/b2d05a8c8b4940ac97bbd4a3ee09c98d.png