原題鏈接
文章目錄
- 思路
- C++代碼
思路
首先：要求二叉樹的每個節點上的值，一定需要遍歷二叉樹，并且要先訪問根節點，在二叉樹的三種遍歷方式中先訪問根節點為二叉樹的前序遍歷，題目要求列印路徑，從根節點到最后的葉節點才是一條路徑，
其次考慮，題干要求回傳的是二叉樹節點路徑，所以我們需要定義一個空間來存放路徑，
再考慮查找的程序，以上題為例子
| 操作 | 路徑 | 節點路徑和 | 目標值 |
|---|---|---|---|
| 入節點10 | 10 | 10 | 22 |
| 入節點5 | 10 5 | 15 | 22 |
| 入節點4 | 10 5 4 | 19 | 22 |
| 路徑和！=目標值回到節點5 | |||
| 洗掉路徑4 | 10 5 | 15 | 22 |
| 入節點7 | 10 5 7 | 22 | 22 |
| 路徑和與目標值相同記錄這個路徑 |
根據上表分析儲存路徑的資料結構為后進先出的形式，所以用堆疊來存盤，
回傳形式
題目最后要求以二維陣列的形式回傳路徑，所以我們用陣列來存盤路徑，只要每次尾插資料，尾刪資料，陣列也可以看作為堆疊，當陣列路徑和與設定的相同時尾插到這個二維陣列上，并且因為要以遞回的形式來遍歷二叉樹，所以我們把二維陣列定義為全域的形式，避免多次遞回帶來的性能損耗
我們在做這種遞回的題的時候要想清楚三步
1.遞回出口，2.子步驟要執行什么，3.遞回條件與路徑
1.遞回出口：左右子樹為空時(葉子節點)，這時還要判斷路徑和與設定值是否相同，結束后還要退回上一個節點，所以還要把這個節點踢出陣列，
2.子步驟：每次遞回到這個節點時要把這個節點的值加到記錄路徑和的變數中，同時還要把這個節點的數字尾插到陣列上
3.遞回條件與路徑：二叉樹的先序遍歷，遞回時當左樹不為空時先遞回左樹，在左樹為空后再遞回右樹
之后再以合理的方式將這三步組織起來
C++代碼
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int>>ret;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root==nullptr)
return ret;
int SumStack=0;//記錄路徑的和
vector<int>Path;//存放路徑
_FindPath(root,expectNumber,Path,SumStack);
return ret;
}
private:
void _FindPath(TreeNode*root,int expectNumber,vector<int>&Path,int SumStack)
{
SumStack=SumStack+root->val;//子步驟
Path.push_back(root->val);
if(root->left)//遞回路徑與遞回條件
{
_FindPath(root->left,expectNumber,Path,SumStack);
}
if(root->right)
{
_FindPath(root->right,expectNumber,Path,SumStack);
}
//遞回出口，在葉子節點要和規定值做對比，相同時尾插到全域的二維陣列中
if(SumStack==expectNumber&&root->left==nullptr&&root->right==nullptr)//葉子節點且有相等的值
{
ret.push_back(Path);
}
Path.pop_back();
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/306228.html
標籤：java
上一篇：初識java的String類
下一篇：StringBuffer類