C++ 二叉树的遍历

前序遍历：

遍历的顺序是：根节点-左节点-右节点

递归代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::function<void(TreeNode*)> order = [&](TreeNode* node){
        if(node == nullptr) return;
        res.push_back(node->val);
        order(node->left);
        order(node->right);
      };
      order(root);
      return res;
    }
};

迭代代码：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()) {
        root = s.top();
        s.pop();
        if(root == nullptr) continue;
        res.push_back(root->val);
        s.push(root->right);
        s.push(root->left);
      }
      return res;
    }
};

中序遍历：

遍历的顺序是：左节点-根节点-右节点

递归代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
        std::function<void(TreeNode*)> order = [&](TreeNode* node){
          if(node == nullptr) return;
          order(node->left);
          res.push_back(node->val);
          order(node->right);
        };
        order(root);
        return res;
    }
};

迭代代码

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode*> s;
      while(root != nullptr || !s.empty()){
        while(root != nullptr){
          s.push(root);
          root = root->left;
        }
        root = s.top();
        s.pop();
        res.push_back(root->val);
        root = root->right;
      }
      return res;
    }
};

后序遍历：

遍历的顺序是：左节点-右节点-根节点

递归代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        std::function<void(TreeNode*)> order = [&](TreeNode* node){
          if(node == nullptr) return;
          order(node->left);
          order(node->right);
          res.push_back(node->val);
        };
        order(root);
        return res;
    }
};

迭代代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
      std::vector<int> res;
      if(root == nullptr) return res;
      std::stack<TreeNode*> s;
      s.push(root);
      while(!s.empty()) {
        root = s.top();
        if(root == nullptr){
          s.pop();
          res.push_back(s.top()->val);
          s.pop();
        } else {
          s.push(nullptr);
          if(root->right) s.push(root->right);
          if(root->left) s.push(root->left);
        }
      }
      return res;
    }
};