程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++完成二叉樹非遞歸遍歷辦法實例總結

C++完成二叉樹非遞歸遍歷辦法實例總結

編輯:關於C++

C++完成二叉樹非遞歸遍歷辦法實例總結。本站提示廣大學習愛好者:(C++完成二叉樹非遞歸遍歷辦法實例總結)文章只能為提供參考,不一定能成為您想要的結果。以下是C++完成二叉樹非遞歸遍歷辦法實例總結正文


普通來講,二叉樹的遍歷是C++法式員在面試中常常考核的,其實前中後三種次序的遍歷都年夜同小異,本身模仿兩個棧用筆劃畫是不難寫出代碼的。現舉一個非遞歸遍歷的辦法以下,供年夜家參考。

詳細代碼以下:

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;
  }
};

願望本文所述對年夜家的C++算法進修有所贊助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved