数据结构-二叉树

二叉树层序遍历

class Solution {
public:
    queue<TreeNode*> ready;//队列中放入准备要记录的节点
    vector<vector<int>> res;//存储最终输出的结果
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)//如果这个树是空的就直接结束
        {
            return res;
        }
        ready.push(root);//先把根节点放进队列中
        while(!ready.empty())//如果队列中没有要记录的节点就结束循环
        {
        int centerSize = ready.size();//记录每一层节点的数量
        vector<int> temp;//用来临时存储这一层的节点值
            for(int i =0;i<centerSize;i++)//把上一层结点全部pop出去 保证下一次循环是第二层
            {
            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;
    }
};
/*
迭代实现



bfs
递归实现层序遍历
子问题就是把根节点的左右子树压入栈中
用一个队列表示要被遍历的根节点 压完一个就d出一个

这一层要做什么 层数+1 把这一层的val压入栈 
要返回什么 是否有左右子树了 有返回true 没有返回false
终止条件是什么 这一层都没有左右子树了
*/

二叉树中序遍历

class Solution {
public:
vector<int> res;
int mid(TreeNode* node)
{
    if(node == nullptr)
        return 0;
    mid(node->left);
    res.push_back(node->val);
    mid(node->right);
    return 0;
};
    vector<int> inorderTraversal(TreeNode* root) {
        mid(root);
        return res;
    }
};
/*
递归遍历 中序遍历 左 根 右
这一节要做什么  输出当前结点的值 
终止条件是什么 如果是空节点就结束
返回给上一级什么 未知
void mid(TreeNode* node)
{
    if(node == null)
        return 0;
    mid(node->left);
    cout<val;
    mid(node->right);
}
*/

二叉树后续遍历 迭代版本

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> 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 要么他是叶子节点 要么就是他的左右结点都被读过了 也就是 右边结点是上一个结点*/

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

    }
};

二叉树前序遍历

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

前序中序生成二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& 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<int> preorder;
    unordered_map<int, int> 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_map<int,int>map;
    vector<int> postorder;
    bool recurser(int root,int left,int right,vector<int> &inOrder)
    {   
        /*中序遍历中postorderroot的位置 */
        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]<postorder[root])
                return false;
        }
        for(int j = (root-rightNum-1);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<int>& postorder) {
        this->postorder =postorder; 
        int size = postorder.size();
        vector<int> inOrder = postorder;
        sort(inOrder.begin(),inOrder.end());
        
        for(int i = 0;i<size;i++)
        {
            map[inOrder[i]] = i;
        }
        return recurser(size-1,0,size-1,inOrder);
        
    }
};
/*最后一个一定是根 
一个后续遍历是无法建立一棵树的 所以不可能生成中序遍历  而且他也没有给树的结构体 说明肯定不要建树 那么 等下 我可以获得中序遍历 从小到大排列一下 那我现在就有后续遍历和中序遍历 那么我
*/
/*
1 3 2 6 5 后续遍历特点 最后一个一定是根节点 紧贴他的那个一定是右结点 那么
1 2 3 5 6 中序遍历特点 通过根节点的位置知道左右子树的数量 那么先知道5 说明左子树3个 有子树1个  
1 6 3 2 5 
1 2 3 5 6 
一样的
*/

/*
递归
left right root
这一层我们要做什么root =  postorder[right]
i = map[root];
if(i!=right)//就说明有右子树
if(map[postorder[right-1]] < map[]postorder[right] )
return false;
右子树recurser(root-1,right + right -i-1,root-1,)
左子树recurser(root-right + i,left,root-right + i)
*/