数据结构-二叉树

class Solution {
public:
    queue ready;//队列中放入准备要记录的节点
    vector> res;//存储最终输出的结果
    vector> levelOrder(TreeNode* root) {
        if(!root)//如果这个树是空的就直接结束
        {
            return res;
        }
        ready.push(root);//先把根节点放进队列中
        while(!ready.empty())//如果队列中没有要记录的节点就结束循环
        {
        int centerSize = ready.size();//记录每一层节点的数量
        vector temp;//用来临时存储这一层的节点值
            for(int i =0;i
            auto center = ready.front();//从队列第一个取出要遍历的节点
            ready.pop();//将给结点从队列中删除
            temp.push_back(center->val);
            if(center->left)//如果有左子树就将该左子树放进队列 并且将值压入栈中
            {
                ready.push(center->left);
                //temp.push_back(center->left->val);
            }
            if(center->right)
            {
                ready.push(center->right);
                //temp.push_back(center->right->val);
            }
            }
            res.push_back(temp);
        }
        return res;
    }
};

class Solution {
public:
vector res;
int mid(TreeNode* node)
{
    if(node == nullptr)
        return 0;
    mid(node->left);
    res.push_back(node->val);
    mid(node->right);
    return 0;
};
    vector inorderTraversal(TreeNode* root) {
        mid(root);
        return res;
    }
};

class Solution {
public:
    vector postorderTraversal(TreeNode* root) {
        stack s;
        vector res;
        if(root == NULL)
        return res;
        //s.push(root);
        TreeNode* pre = NULL;
        while(root!=NULL||!s.empty())
        {
            while(root!= NULL)
            {
                s.push(root);
                root = root->left;
            }
            root = s.top();//此时获取的是上面root结点的最左边那个结点
            //s.pop();
            if(root->right!= NULL&&root->right!= pre)//如果这个节点有右结点就把右结点放进去
            {
                //s.push(root);
                root = root->right;
            }
            else
            {
                pre = root;
                res.push_back(root->val);
                s.pop();
                root = NULL;
            }
            

            //res.push_back(root->val);
        }
        return res;

    }
};

class Solution {
public:
        vector res;
    void cersion(TreeNode* root)
    {
        if(!root)
        {
            return;
        }
        res.push_back(root->val);
        cersion(root->left);
        cersion(root->right);
    }
    vector preorderTraversal(TreeNode* root) {
        cersion(root);
        return res;
    }
};

class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            dic[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector preorder;
    unordered_map dic;
    TreeNode* recur(int root, int left, int right) { //root是根节点的位置 left和right是该区间的左右范围 这些都是先序遍历中的
        if(left > right) return nullptr;                        // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic[preorder[root]];                            // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                            // 回溯返回根节点
    }
};

class Solution {
public:
    unordered_mapmap;
    vector postorder;
    bool recurser(int root,int left,int right,vector &inOrder)
    {   
        
        if(root<0)
        return true;
        int i = map[postorder[root]];
        int rightNum = right - i;
        int leftNum = i-left;
        if(left >= right)
            return true;
        for(int j = root-1;j>(root-rightNum);j--)
        {
            if(postorder[j]root-rightNum-1-leftNum;j--)
        {
            if(postorder[j]>postorder[root])
            return false;
        }
        
        return recurser(root-1,i+1,right,inOrder)&&recurser(root - rightNum-1,left,i-1,inOrder);
    }
    bool verifyPostorder(vector& postorder) {
        this->postorder =postorder; 
        int size = postorder.size();
        vector inOrder = postorder;
        sort(inOrder.begin(),inOrder.end());
        
        for(int i = 0;i
            map[inOrder[i]] = i;
        }
        return recurser(size-1,0,size-1,inOrder);
        
    }
};