快捷導(dǎo)航

C++實(shí)現(xiàn)二叉樹非遞歸遍歷方法實(shí)例總結(jié)

更新時(shí)間：2014年08月27日 11:27:05 投稿：shichen2014

這篇文章主要介紹了C++實(shí)現(xiàn)二叉樹非遞歸遍歷方法實(shí)例總結(jié),是算法設(shè)計(jì)中比較經(jīng)典的一個(gè)遍歷算法,需要的朋友可以參考下

一般來說，二叉樹的遍歷是C++程序員在面試中經(jīng)?？疾斓?，其實(shí)前中后三種順序的遍歷都大同小異，自己模擬兩個(gè)棧用筆畫畫是不難寫出代碼的。現(xiàn)舉一個(gè)非遞歸遍歷的方法如下，供大家參考。

具體代碼如下：

class Solution {
public:
  vector<int> preorderTraversal(TreeNode *root) {
    vector<int> out;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty() && root){
      TreeNode *node = s.top();
      out.push_back(node->val);
      s.pop();
      if(node->right) s.push(node->right);
      if(node->left) s.push(node->left);
    }
    return out;
  }
  vector<int> inorderTraversal(TreeNode *root) {
    stack<TreeNode *> s;
    vector<int> out;
    TreeNode *node = root;
    bool done = false;
    while(!done){
      if(node){
        s.push(node);
        node = node->left;
      }else {
        if(s.empty()) done = true;
        else{
          node = s.top();
          s.pop();
          out.push_back(node->val);
          node = node->right;
        }
      }
    }
    return out;
  }
  vector<int> postorderTraversal(TreeNode *root) {
    vector<int> out;
    stack<TreeNode*> s;
    TreeNode* node = root;
    s.push(node);
    while(!s.empty()&&node){
      node = s.top();
      out.push_back(node->val);
      s.pop();
      if(node->left) s.push(node->left);
      if(node->right)s.push(node->right);
    }
    reverse(out.begin(),out.end());
    return out;
  }
};

希望本文所述對(duì)大家的C++算法學(xué)習(xí)有所幫助。

您可能感興趣的文章:

相關(guān)文章

C語言鏈表實(shí)現(xiàn)貪吃蛇游戲
這篇文章主要為大家詳細(xì)介紹了C語言鏈表實(shí)現(xiàn)貪吃蛇游戲源碼，適合C語言入門者學(xué)習(xí)閱讀，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2017-10-10
最大對(duì)稱字符串的算法
題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。
2013-03-03
C語言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問題解析
循環(huán)隊(duì)列又叫環(huán)形隊(duì)列，是一種特殊的隊(duì)列。循環(huán)隊(duì)列解決了隊(duì)列出隊(duì)時(shí)需要將所有數(shù)據(jù)前移一位的問題，本篇帶你一起看看循環(huán)隊(duì)列的問題和怎樣用隊(duì)列實(shí)現(xiàn)棧
2022-04-04
C++ vector類的模擬實(shí)現(xiàn)方法
這篇文章主要介紹了C++ vector類的模擬實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-05-05
C++實(shí)現(xiàn)LeetCode( 69.求平方根)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode( 69.求平方根),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
OpenCV利用背景建模檢測(cè)運(yùn)動(dòng)物體
這篇文章主要為大家詳細(xì)介紹了OpenCV利用背景建模檢測(cè)運(yùn)動(dòng)物體，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-01-01
C++中引用傳遞與指針傳遞的區(qū)別(面試常見)
這篇文章主要介紹了C++中引用傳遞與指針傳遞的區(qū)別(面試常見),需要的朋友可以參考下
2018-03-03
Sublime Text 3 實(shí)現(xiàn)C++代碼的編譯和運(yùn)行示例
下面小編就為大家?guī)硪黄猄ublime Text 3 實(shí)現(xiàn)C++代碼的編譯和運(yùn)行示例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-09-09
C++實(shí)現(xiàn)寵物商店信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)寵物商店信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03
C語言實(shí)現(xiàn)煙花表白程序代碼
大家好，本篇文章主要講的是C語言實(shí)現(xiàn)煙花表白程序代碼，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下
2022-02-02