题解 | #二叉树的前序遍历#

没啥好讲的，树的遍历只有在迭代中才比较复杂

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> traverse;
      
      preorder_traverse(root, traverse);
      
      return traverse;
    }
  private:
    void preorder_traverse(TreeNode *root, std::vector<int> &traverse) {
      if (root == nullptr) {
        return ;
      } 
      traverse.push_back(root->val);
      preorder_traverse(root->left, traverse);
      preorder_traverse(root->right, traverse);
    }
};

这里写个迭代吧

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
      std::vector<int> res;
      std::stack<TreeNode *> stack_;
      
        //  根节点为空返回空的vector容器
      if (root == nullptr) {
        return res;
      }
      
        //  非空先访问更结点
      res.push_back(root->val);
      
        //  这里注意
        //  递归是先访问左子树
        //  但是栈是先进后出，需要反着来
      if (root->right) {
        stack_.push(root->right);
      }
      
      if (root->left) {
        stack_.push(root->left);
      }
      
        //  重复取出根节点、压入右子树、再压入左子树，直到遍历完，容器为空
        //  对应递归，取出根节点，遍历左子树，再遍历右子树
      while (!stack_.empty()) {
        TreeNode *root = stack_.top();
        stack_.pop();
        res.push_back(root->val);
        if (root->right) {
          stack_.push(root->right);
        }
        if (root->left) {
          stack_.push(root->left);
        }
      }
      
      return res;
    }
};