二叉樹的問題，一定要明白到底應(yīng)該深度優(yōu)先（前中后序）還是廣度優(yōu)先（層序遍歷）
最基本的遍歷方式：深度優(yōu)先和廣度優(yōu)先
深度優(yōu)先：前、中、后序（遞歸法和迭代法均可）
廣度優(yōu)先：層次遍歷（迭代法）
棧其實就是遞歸的一種實現(xiàn)結(jié)構(gòu)，也就是說前中后序遍歷的邏輯其實都是可以借助棧使用非遞歸的方式來實現(xiàn)的；
廣度優(yōu)先遍歷（層序遍歷）的實現(xiàn)一般使用隊列來實現(xiàn)，這也是隊列先進先出的特點所決定的，因為需要先進先出的結(jié)構(gòu)，才能一層一層的來遍歷二叉樹。
二叉樹節(jié)點的定義框架：
復制代碼
struct TreeNode {
? ? int val;
? ? TreeNode *left;
? ? TreeNode *right;
? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
復制代碼
二叉樹的遞歸遍歷框架：
復制代碼
/*二叉樹的遍歷框架*/
void traverse(TreeNode root)
{
? ? //前序遍歷：先訪問根節(jié)點，再前序訪問左子樹，再訪問右子樹
? ? traverse(root->left);
? ? //中序遍歷：先中序訪問左子樹，再訪問根節(jié)點，再訪問右子樹
? ? traverse(root->right);
? ? //后續(xù)遍歷：先后續(xù)訪問左子樹，再訪問右子樹，再訪問根節(jié)點
}
復制代碼
一、二叉樹的前序遍歷：迭代和遞歸
復制代碼
class Solution {
public:
? ? //vector<int> result;//遞歸的話定義在這里
? ? vector<int> preorderTraversal(TreeNode* root) {
? ? ? ? //遞歸方式
? ? ? ? /*
? ? ? ? if(root == nullptr)
? ? ? ? ? ? return {};
? ? ? ? result.push_back(root->val);
? ? ? ? preorderTraversal(root->left);
? ? ? ? preorderTraversal(root->right);
? ? ? ? return result;
? ? ? ? */
? ? ? ? //當然可以使用迭代解法，因為遞歸本身就是用棧來實現(xiàn)的，可以通過棧來迭代操作
? ? ? ? //但是要注意棧的特性是后入先出，前序的話，就是先放入根節(jié)點賦值操作彈出，再放入右節(jié)點、左節(jié)點，再彈出，這樣左節(jié)點就會先出，先賦值操作，就是前序了
? ? ? ? stack<TreeNode*> sta;
? ? ? ? vector<int> result;
? ? ? ? sta.push(root);
? ? ? ? while(!sta.empty()) {
? ? ? ? ? ? int size = sta.size();
? ? ? ? ? ? for(int i=0; i<size; i++) {
? ? ? ? ? ? ? ? TreeNode* node = sta.top();
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? result.push_back(node->val);
? ? ? ? ? ? ? ? if(node->right)
? ? ? ? ? ? ? ? ? ? sta.push(node->right);
? ? ? ? ? ? ? ? if(node->left)
? ? ? ? ? ? ? ? ? ? sta.push(node->left);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return result;
? ? }
};
復制代碼
二、二叉樹的后序遍歷：迭代和遞歸
復制代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
*? ? int val;
*? ? TreeNode *left;
*? ? TreeNode *right;
*? ? TreeNode() : val(0), left(nullptr), right(nullptr) {}
*? ? TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*? ? TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
? ? //vector<int> result;//遞歸解法定義在這里
? ? vector<int> postorderTraversal(TreeNode* root) {
? ? ? ? /*
? ? ? ? if(root == nullptr)
? ? ? ? ? ? return {};
? ? ? ? postorderTraversal(root->left);
? ? ? ? postorderTraversal(root->right);
? ? ? ? result.push_back(root->val);
? ? ? ? return result;
? ? ? ? */
? ? ? ? //本題還可以采用迭代解法，因為遞歸就是用棧來實現(xiàn)的
? ? ? ? //考慮實現(xiàn)的過程
? ? ? ? //后序遍歷是左右中的順序，但是我們在迭代的時候肯定會先訪問根節(jié)點，也就是中間的節(jié)點，所以考慮先訪問和處理中間節(jié)點，再處理右節(jié)點，再處理左邊節(jié)點，最后將結(jié)果翻轉(zhuǎn)就行了
? ? ? ? stack<TreeNode*> sta;
? ? ? ? vector<int> result;
? ? ? ? sta.push(root);
? ? ? ? while(!sta.empty()) {
? ? ? ? ? ? int size = sta.size();
? ? ? ? ? ? for(int i=0; i<size; i++) {
? ? ? ? ? ? ? ? TreeNode* node = sta.top();
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? result.push_back(node->val);
? ? ? ? ? ? ? ? if(node->left)
? ? ? ? ? ? ? ? ? ? sta.push(node->left);
? ? ? ? ? ? ? ? if(node->right)
? ? ? ? ? ? ? ? ? ? sta.push(node->right);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? reverse(result.begin(), result.end());
? ? ? ? return result;
? ? }
};
復制代碼
三、二叉樹的中序遍歷：迭代和遞歸
復制代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
*? ? int val;
*? ? TreeNode *left;
*? ? TreeNode *right;
*? ? TreeNode() : val(0), left(nullptr), right(nullptr) {}
*? ? TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*? ? TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
? ? //vector<int>result;//遞歸寫法這里定義
? ? vector<int> inorderTraversal(TreeNode* root) {
? ? ? ? /*遞歸解法
? ? ? ? if(root == nullptr)
? ? ? ? ? ? return {};
? ? ? ? inorderTraversal(root->left);
? ? ? ? result.push_back(root->val);
? ? ? ? inorderTraversal(root->right);
? ? ? ? return result;
? ? ? ? */
? ? ? ? //還能采用迭代解法，用棧來解決，因為遞歸本身就是用棧來實現(xiàn)的，因此是完全行得通的
? ? ? ? //中序的順序是左中右，那出棧的時候，處理的順序肯定是右中左
? ? ? ? //搞清楚訪問和處理的概念
? ? ? ? //訪問：將節(jié)點入棧
? ? ? ? //處理：將節(jié)點的值放入結(jié)果集
? ? ? ? //中序的訪問和處理的順序是不一樣的，所以要借助指針進行訪問，也就是將節(jié)點放入棧中，用棧來做處理，也就是放入結(jié)果集
? ? ? ? vector<int> result;
? ? ? ? stack<TreeNode*> sta;
? ? ? ? TreeNode* cur = root;
? ? ? ? while(cur != nullptr || !sta.empty()) {
? ? ? ? ? ? if(cur != nullptr) {//指針用來訪問節(jié)點，訪問到左邊最底層的時候，指針和要開始處理的位置就一樣了
? ? ? ? ? ? ? ? sta.push(cur);//將訪問的節(jié)點放進棧
? ? ? ? ? ? ? ? cur = cur->left;//最左的子節(jié)點最后放進去，所以會先出棧? ? 左
? ? ? ? ? ? }
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? cur = sta.top();
? ? ? ? ? ? ? ? sta.pop();
? ? ? ? ? ? ? ? result.push_back(cur->val);? ? ? ? ? ? ? ? ? ? ? ? ? ? //中
? ? ? ? ? ? ? ? cur = cur->right;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //右
? ? ? ? ? ? }
? ? ? ? }
? ? }
};
復制代碼
四、二叉樹的層序遍歷：迭代和遞歸
復制代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
*? ? int val;
*? ? TreeNode *left;
*? ? TreeNode *right;
*? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
? ? vector<vector<int>> levelOrder(TreeNode* root) {
? ? ? ? queue<TreeNode*> que;//創(chuàng)建一個隊列，層序遍歷樹的需要用隊列來實現(xiàn)，隊列中是二叉樹的節(jié)點
? ? ? ? if(root != nullptr)
? ? ? ? ? ? que.push(root);//如果頭結(jié)點不為空的話，先將頭結(jié)點放到隊列中，因為頭結(jié)點也就是第一行，只有這一個元素，所以直接放進去
? ? ? ? vector<vector<int>> result;//定義返回值，返回的是一個二維數(shù)組
? ? ? ? while(!que.empty()) {
? ? ? ? ? ? int size = que.size();//同一行可能不止一個元素，要循環(huán)都進行遍歷，又因為下面要進行pop操作，que.size()是一個變化的值，所以這里存儲數(shù)量
? ? ? ? ? ? vector<int> vec;//用于臨時存儲每一行的節(jié)點值，最后統(tǒng)一存入返回的二維數(shù)組中
? ? ? ? ? ? for(int i=0; i<size; i++) {
? ? ? ? ? ? ? ? TreeNode* node = que.front();
? ? ? ? ? ? ? ? que.pop();//
? ? ? ? ? ? ? ? vec.push_back(node->val);
? ? ? ? ? ? ? ? if(node->left)
? ? ? ? ? ? ? ? ? ? que.push(node->left);//將這個節(jié)點的左右子節(jié)點放入隊列中
? ? ? ? ? ? ? ? if(node->right)
? ? ? ? ? ? ? ? ? ? que.push(node->right);
? ? ? ? ? ? }
? ? ? ? ? ? result.push_back(vec);
? ? ? ? }
? ? ? ? return result;
? ? }
};
復制代碼
深圳網(wǎng)站建設(shè)www.sz886.com
