二叉树的深度优先遍历（力扣94-中序；145-后序；144前序）

144-二叉树的前序遍历

前序遍历定义：按照D->L->R的顺序访问节点

1. 先访问根节点D
2. 按照先序次序遍历D的左子树
3. 按照先序次序访问D的右子树

class Solution {
public:

void preorder(TreeNode *root,vector &res){
        // 专门在写一个函数用来递归
        if(root == nullptr){
            // 出口条件是遇到根节点
            return;
        }
        res.push_back(root->val);// 把根节点的值插入数组
        preorder(root->left,res);// 先序遍历左子树
        preorder(root->right,res);// 先序遍历右子树
    }

    vector preorderTraversal(TreeNode* root) {
        // 传入参数是一个指针，指向数据结构为”节点“的根节点
        vector res;// 这是用来保存遍历结果的数组
        preorder(root,res);
        return res;
    }
};

但是我感觉我不是很看得懂这个输入，他输入的是一个数组？感觉跟它定义的节点结构体对不上啊

 * 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) {}
 * };

接下来尝试一下迭代写法，官方题解中是这么说的：递归写法相当于隐式维护了一个栈，而迭代就是要把这个栈写出来

    vector preorderTraversql(TreeNode *root){

        vector res;

        if(root=nullptr){
            return res;
        }

        stack stk;
        TreeNode* node = root;
    
        while(!stk.empty() || node!=nullptr){
        // 栈非空 或 根节点不为空

        // 这个循环是用来访问左节点，过程中把值写入数组和栈
        while(node != nullptr){
            // emplace是C++11提供的新方法，功能上和push差不多
            res.emplace_back(node->val);
            stk.emplace(node);
            // 用传入的参数调用构造函数，在栈顶生成对象
            node = node->left;
        }
        node = stk.top();// 此时的栈顶应该是最深的那个左节点
        // 这一句其实相当于折返，本来此时node=null，因为左节点为空
        // 此时当前根节点的左子树就放问完了，接下来访问当前根节点的右子树
        stk.pop();
        node = node->right;
        // 当右节点也为空时
        }
        return res;
    }

啊啊啊……好复杂，要操作一个栈来实现算法

94-二叉树的中序遍历

访问左子树->根节点->右子树

与前序遍历同理，仍旧使用递归的话改一句顺序就可以了

但是同样的代码，这里的时间效率特别低

145-二叉树的后序遍历

访问左子树->右子树->根节点

与前序遍历同理，仍旧使用递归的话改一句顺序就可以了

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        vector ret;
        if(root!=nullptr){
            Auxiliary(root,ret);
        }
        return ret;
    }

    void Auxiliary(TreeNode* root,vector &ret){
        if(root==nullptr) return;
        // 后序递归遍历左子树
        Auxiliary(root->left,ret);
        // 后序递归遍历右子树
        Auxiliary(root->right,ret);
        // 访问根节点
        ret.insert(ret.end(),root->val);
    }
};

发现一样的代码每次提交结果还不一样了??