【C/C++練習題】二叉樹中和為某一值的路徑

《劍指Offer》面試題34：二叉樹中和為某一值的路徑

1 題目

輸入一棵二叉樹和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑。從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑

2 分析

本題目的是找出所有符合條件的路徑，是以要周遊二叉樹，使用先序周遊可以從根節點開始。

需要一個輔助空間存儲周遊過的樹節點。當程式周遊到葉子節點的時候，如果滿足所有路徑和為指定值，列印路徑。

在遞歸周遊節點過程中，當程式周遊完一條完整的路徑，需要退回上一級父節點，此時也在路徑中删除目前節點。

3 代碼

/*
*********************************************************************************************************
*
* 子產品名稱 : 主程式
* 檔案名稱 : demo.cpp
* 版    本 : V1.0
* 說    明 : 《劍指Offer》筆試題，二叉樹和為某一值得路徑
*
* 修改記錄 :
*  版本号	日期        	作者 	說明
*  V1.0		2019-08-13 	hinzer  正式釋出
*
* 碼雲連結：
*
*********************************************************************************************************
*/

#include "iostream"
#include "cstdlib"
#include <vector>

using namespace std;


typedef struct Node
{
	int m_nValue;
	Node* m_pLeft;
	Node* m_pRight;
}BinaryTreeNode;	

void FindPath(BinaryTreeNode* pNode, int expectedSum);
void FindPath(BinaryTreeNode* pNode, vector<int> &path , int expectedSum);

/******************************************************************************
* 函數介紹：确定二叉樹和為某一值得路徑
* 輸入參數：pNode二叉樹頭節點指針, expectedSum期望路徑和
* 輸出參數：無
* 傳回值：無
* 備注：無
******************************************************************************/
void FindPath(BinaryTreeNode* pNode, int expectedSum)
{	
	if (NULL == pNode)
		return ;

	vector<int> path;
	FindPath(pNode, path, expectedSum);
}

/******************************************************************************
* 函數介紹：确定二叉樹和為某一值得路徑
* 輸入參數：pNode二叉樹頭節點指針, path存儲路徑, expectedSum期望路徑和
* 輸出參數：無
* 傳回值：無
* 備注：無
******************************************************************************/
void FindPath(BinaryTreeNode* pNode, vector<int> &path , int expectedSum)
{	

	path.push_back(pNode->m_nValue);	//插入節點數值

	//1.回歸條件--确定為葉子節點
	if ((NULL == pNode->m_pLeft) && (NULL == pNode->m_pRight))
	{
		if (pNode->m_nValue == expectedSum)
		{
			cout << "a path is found:";
			vector<int>::iterator iter = path.begin();
			for(;iter != path.end();++iter)
			{
				cout << *iter << "-";
			}
			cout << endl;
		}
	}

	//2.不是葉子節點，對子節點進行遞歸調用
	if (NULL != pNode->m_pLeft)
		FindPath(pNode->m_pLeft, path, expectedSum - pNode->m_nValue);

	if (NULL != pNode->m_pRight)
		FindPath(pNode->m_pRight, path, expectedSum - pNode->m_nValue);

	path.pop_back();	//退回父節點，在路徑上要三處目前節點
}



/******************************************************************************
* 函數介紹：功能測試函數
* 輸入參數：無
* 輸出參數：無
* 傳回值：無
* 備注：無
******************************************************************************/
void test01()
{
//                8(node1)
//        6(node2)      10(node3)
//  5(node4) 13(node5) 9(node6)  11(node7)
	BinaryTreeNode* node1  = new BinaryTreeNode();
	BinaryTreeNode* node2  = new BinaryTreeNode();
	BinaryTreeNode* node3  = new BinaryTreeNode();
	BinaryTreeNode* node4  = new BinaryTreeNode();
	BinaryTreeNode* node5  = new BinaryTreeNode();
	BinaryTreeNode* node6  = new BinaryTreeNode();
	BinaryTreeNode* node7  = new BinaryTreeNode();
 
	//node1
	node1->m_nValue = 8;
	node1->m_pLeft = node2;
	node1->m_pRight = node3;
 
	//node2
	node2->m_nValue = 6;
	node2->m_pLeft = node4;
	node2->m_pRight = node5;
 
	//node3
	node3->m_nValue = 10;
	node3->m_pLeft = node6;
	node3->m_pRight = node7;
 
	//node4
	node4->m_nValue = 5;
	node4->m_pLeft = nullptr;
	node4->m_pRight = nullptr;	
 
	//node5
	node5->m_nValue = 13;
	node5->m_pLeft = nullptr;
	node5->m_pRight = nullptr;	
 
	//node6
	node6->m_nValue = 9;
	node6->m_pLeft = nullptr;
	node6->m_pRight = nullptr;	
 
	//node7
	node7->m_nValue = 11;
	node7->m_pLeft = nullptr;
	node7->m_pRight = nullptr;	
 
	//測試部分
	FindPath(node1, 27);


	delete node1;delete node2;
	delete node3;delete node4;
	delete node5;delete node6;
	delete node7;
 
}



int main(int argc, char const *argv[])
{
	test01();
	return 0;
}
           

4 運作結果