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

方法一：递归

二叉树的前序遍历顺序：根节点->左节点->右节点。先保存根节点的值，依次进入左右子树进行递归。

时间复杂度：o(n)。需要遍历二叉树的所有节点，需要o(n)。

空间复杂度：o(n)。需要开辟空间保存前序遍历的节点值。

class Solution {
  public:
    void pre_search(TreeNode* root, vector<int>& pre_tree) {
	  	//当节点为空时返回
        if (root == nullptr)
            return;

        //保存根节点的值
        pre_tree.push_back(root->val);
        //遍历左节点
        pre_search(root->left, pre_tree);
        //遍历右节点
        pre_search(root->right, pre_tree);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> pre_tree;
        pre_search(root, pre_tree);
        return pre_tree;
    }
};

方法二：栈（非递归）

根据栈先进后出的特性，本题可以将递归转换为栈来求解。

二叉树的前序遍历顺序：根节点->左节点->右节点。根据栈先进后出的特性，所以需要先将结点的右结点压入栈中，再将左结点压入栈中。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> pre;
        //特殊情况处理
        if (root == nullptr)
            return pre;
		//辅助栈
        stack<TreeNode*> temp;
        temp.push(root);
        
        while (!temp.empty()) {
            TreeNode* node = temp.top();
		  	//每次栈顶就是写入到数组中的元素
            pre.push_back(node->val);
            temp.pop();
            //先将右结点压入栈中，再将左结点压入栈中
            if (node->right != nullptr)
                temp.push(node->right);
            if (node->left != nullptr)
                temp.push(node->left);
        }

        return pre;
    }
};