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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 方法一：使用递归的方法，必须能够信手沾来；
 方法二：使用非递归的方法，使用的是栈结构，也必须能够信手沾来；栈刚好和递归的顺序想法操作，
 
 有一个很明确的宗旨：凡是可以使用递归的地方，都可以使用栈来实现，以提高效率；
 因为递归是用栈结构来实现的，而递归有需要额外的开销；（函数指针以及参数的保存，读取和销毁操作）
 
 * };
 */
class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   *
   * @param root TreeNode类
   * @return int整型vector
   */

  vector<int> preorderTraversal(TreeNode* root) {
    // recursive
    //return PreOrderTraversalRecursive(root);

    // not recursive
    return PreOrderTraversalNotRecursive(root);
  }

  // recursive
  vector<int> PreOrderTraversalNotRecursive(TreeNode* root) {
    vector<int> vi;
    if (root == nullptr) return vi;
    
    stack<TreeNode*> si;
    si.push(root);

    while (!si.empty()) {
      auto cur_node = si.top();
      si.pop();

      vi.push_back(cur_node->val);

      if (cur_node->right != nullptr)
        si.push(cur_node->right);
      
      if (cur_node->left != nullptr)
        si.push(cur_node->left);
    }

    return vi;
  }


  // recursive
  vector<int> PreOrderTraversalRecursive(TreeNode* root) {
    // write code here
    vector<int> vi;
    if (root == nullptr) return vi;

    PreOrderTraversal(root, vi);
    return vi;
  }

  void PreOrderTraversal(TreeNode* root, vector<int>& vi) {
    if (root == nullptr)
      return;

    vi.push_back(root->val);
    if (root->left != nullptr)
      PreOrderTraversal(root->left, vi);

    if (root->right != nullptr)
      PreOrderTraversal(root->right, vi);
  }
};