leetcode 链接：二叉树的前序遍历

题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

解答 & 代码

解法一：递归

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     void preOrder(TreeNode* root, vector<int>& result)
  15.     {
  16.         if(root == nullptr)
  17.             return;
  19.         result.push_back(root->val);
  20.         preOrder(root->left, result);
  21.         preOrder(root->right, result);
  22.     }
  23. public:
  24.     vector<int> preorderTraversal(TreeNode* root) {
  25.         vector<int> result;
  26.         preOrder(root, result);
  27.         return result;
  28.     }
  29. };

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 41.38% 的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了59.64% 的用户

解法二：迭代

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;

        stack<TreeNode*> nodeS;
        while(root != nullptr || !nodeS.empty())
        {
            while(root != nullptr)
            {
                result.push_back(root->val);    // 先访问当前节点，将当前节点的值存储到结果数组中
                nodeS.push(root->right);        // 将当前节点的右子树节点入栈
                root = root->left;                // 访问左子树
            }

            root = nodeS.top();
            nodeS.pop();
        }

        return result;
    }
};

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 41.56% 的用户
内存消耗：8.1 MB, 在所有 C++ 提交中击败了 81.67% 的用户

另一个更好理解的版本：

  • 因为前序遍历先打印左子树再打印右子树（即出栈顺序先左子树再右子树），所以进栈顺序先右子树再左子树

    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
      vector<int> result;
      if(root == nullptr)
          return result;

      stack<TreeNode*> nodeS;
      nodeS.push(root);    // 先将根节点压入栈
      while(!nodeS.empty())
      {
          // 打印当前节点
          TreeNode* node = nodeS.top();
          nodeS.pop();
          result.push_back(node->val);
          // 先将右子树压入栈
          if(node->right != nullptr)
              nodeS.push(node->right);
          // 再将左子树压入栈
          if(node->left != nullptr)
              nodeS.push(node->left);
      }

      return result;
  }
};