题目

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

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内

• -100 <= Node.val <= 100

  
  进阶：递归算法很简单，你可以通过迭代算法完成吗？

  解题方法

  递归

  通过递归的方式前序遍历二叉树，终止节点为当前节点为空。
  时间复杂度O(n)，空间复杂度 平均：O(logn)，最劣（链）：O(n)
  C++代码：

  /**
  * 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:
    void pre_order(TreeNode* p, vector<int>& vec) {
        if(p!=NULL) {
            vec.push_back(p->val);
            pre_order(p->left, vec);
            pre_order(p->right, vec);
        }
    }
  
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        pre_order(root, result);
        return result;
    }
  };
  

  迭代

  使用 栈 处理节点，将栈顶元素（父节点）压入数组后从栈中弹出，再将该节点的右、左节点依次压入栈中，重复该操作直至栈为空。
  时间复杂度 O(n)，空间复杂度 平均：O(logn)，最劣（链）：O(n)
  C++代码：

  /**
  * 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:
    void pre_order(TreeNode* p, vector<int>& vec) {
        stack<TreeNode*> nodes;
        if(p!=NULL) nodes.push(p);
        while(nodes.size()>0) {
            TreeNode *tmp = nodes.top();
            vec.push_back(tmp->val);
            nodes.pop();
            if(tmp->right != NULL) nodes.push(tmp->right);
            if(tmp->left != NULL) nodes.push(tmp->left);
        }
    }
  
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        pre_order(root, result);
        return result;
    }
  };
  

  Morris遍历

  记作当前节点为cur。

1. 如果cur无左孩子，cur向右移动（cur=cur.right）
2. 如果cur有左孩子，找到cur左子树上最右的节点，记为mostright
   1. 如果mostright的right指针指向空，让其指向cur，cur向左移动（cur=cur.left）
   2. 如果mostright的right指针指向cur，让其指向空，cur向右移动（cur=cur.right）

时间复杂度为O(n)，空间复杂度为O(1)。
C++代码：

/**
 * 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==NULL)  return result;

        TreeNode *cur, *mostright;
        cur = root;
        mostright = NULL;
        while(cur!=NULL) {
             mostright = cur->left;
            if(mostright != NULL) {
                while(mostright->right!=NULL && mostright->right!=cur) mostright = mostright->right;

                if(mostright->right == NULL) {
                    result.push_back(cur->val);
                    mostright->right = cur;
                    cur = cur->left;
                }
                else {
                    mostright->right = NULL;
                    cur = cur->right;
                }
            }
            else {
                result.push_back(cur->val);
                cur = cur->right;
            }
        }

        return result;
    }
};

标记法（二叉树遍历的统一写法）

设置标志位来判别节点是否二次访问，对二次访问的节点压入数组。
时间复杂度O(n)，空间复杂度O(logn)，最劣O(n)
C++代码：

/**
 * 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;
        if(root != nullptr)     nodes.push(root);

        while(nodes.size()>0) {
            TreeNode *tmp = nodes.top();
            if(tmp != NULL) {
                nodes.pop();
                if(tmp->right != nullptr)   nodes.push(tmp->right);
                if(tmp->left != nullptr)    nodes.push(tmp->left);
                nodes.push(tmp);
                nodes.push(NULL);
            }
            else {
                nodes.pop();
                tmp = nodes.top();
                result.push_back(tmp->val);
                nodes.pop();
            }
        }

        return result;
    }
};