[数据结构与算法]二叉树的前中序遍历非递归实现 +例题

1.前序遍历

前序遍历顺序? ?根节点->左节点->右节点

??

? ?1.很多时候我们只会利用递归去让计算机去实现遍历 我们可以新增一个例题去理解二叉树 前序遍历

2.递归其实就是通过栈实现 ，我们可以通过数据结构自己创造一个栈去自我完成计算机完成的工作

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
             vector<int>res;
        if(root==NULL){
            return res;//记住任何函数上来引用参数都应该进行判空
        }
        stack<TreeNode *>s;
        while(!s.empty()|| root!=NULL){
            while(root!=NULL){
                res.push_back(root->val);//访问根节点
                s.push(root);
                root=root->left;//访问左节点
            }
            root=s.top();
            s.pop();
            root=root->right;//访问右节点
        }
        return res;

    }
};

2.二叉树中序遍历

?二叉树中序遍历顺讯就是先访问左节点->根节点->最后访问右节点 然后递归就可以变成子树

2.代码实现

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
         vector<int>res;
        if(root==NULL) {
            return res;
        }
        stack<TreeNode *>s;
        while(!s.empty()|| root!=NULL){
            while(root!=NULL){
                s.push(root);
                root=root->left;//访问左节点
            }
            root=s.top();
            s.pop();
            res.puh_back(root->val);//根节点
            root=root->right;//访问右节点
        }
    }
};