leetcode每日一题41

99. 恢复二叉搜索树

中序遍历树，找到逆序的两个数，交换
有两种情况
如果是像示例1一样的，中序遍历后是3，2，1
是连续的两个逆序，那么交换第一，第三个数
如果是像示例2一样，中序遍历后是1，3，4，2
是一个逆序，那么交换这两个数即可

class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* root){
        if(root==nullptr)
            return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
    void recover(TreeNode* root,int count,int x,int y){
        if(root!=nullptr){
            if(root->val==x||root->val==y)
            {
                if(root->val==x)
                    root->val=y;
                else root->val=x;
                if(--count==0)
                    return;
            }
        }
        if (root->left != nullptr) {
            recover(root->left, count, x, y);
        }
        if (root->right != nullptr) {
            recover(root->right, count, x, y);
        }
        return;
    }
    int index1=-1,index2=-1;
    void recoverTree(TreeNode* root) {
        traversal(root);
        for(int i=1;i<vec.size();i++)
        {
            if(vec[i-1]>vec[i])
            {
                index2=i;
                if(index1==-1)
                    index1=i-1;
                else break;
            }
        }
        cout<<index1<<index2<<endl;
        recover(root,2,vec[index1],vec[index2]);
    }
};

102.二叉树的层序遍历

模板，记住就行了
借用?个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，
用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
用result保存层序遍历的结果
用vec保存一层的结果
用que保存该层的子节点

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        vector<vector<int>> result;
        while(!que.empty())
        {
            int size=que.size();
            vector<int> vec;
            for(int i=0;i<size;i++)
            {
                TreeNode* node=que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

103.二叉树的锯齿形层序遍历

在奇数次遍历次数时，reverse一下该层vec就行了

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        int level=0;
        if(root!=nullptr)
            que.push(root);
        vector<vector<int>> result;
        while(!que.empty())
        {
            int size=que.size();
            vector<int> vec;
            for(int i=0;i<size;i++)
            {
                TreeNode* node=que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            if(level%2)
                reverse(vec.begin(),vec.end());
            level++;
            result.push_back(vec);
        }
        return result;
    }
};

或者使用双端队列deque保存该层的节点

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=nullptr)
            que.push(root);
        vector<vector<int>> result;
        bool isOrderLeft = true;
        while(!que.empty())
        {
            int size=que.size();
            deque<int> level;
            for(int i=0;i<size;i++)
            {
                TreeNode* node=que.front();
                que.pop();
                if(isOrderLeft)
                	level.push_back(node->val);
                else level.push_front(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            isOrderLeft=!isOrderLeft;
            result.push_back(vector<int>{level.begin(), level.end()});
        }
        return result;
    }
};

105. 从前序与中序遍历序列构造二叉树

用前序遍历的节点分割中序遍历序列
将中序遍历分为左右子树
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取前序数组第一个元素作为节点元素。
第三步：找到前序数组第一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，?定是先
切中序数组）
第五步：切割前序数组，切成前序左数组和前序右数组
第六步：递归处理左区间和右区间
模板：

TreeNode* traversal (vector& preorder, vector& inorder) {
// 第一步
if (preorder.size() == 0) return NULL;
// 第二步：前序遍历数组第一个元素，就是当前的中间节点
int rootValue = preorder[preorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (preorder.size() == 1) return root;
// 第三步：找切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size();
delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 第四步：切割中序数组，得到 中序左数组和中序右数组
// 第五步：切割前序数组，得到前序左数组和前序右数组
// 第六步
root->left = traversal(前序左数组, 中序左数组);
root->right = traversal(前序右数组, 中序右数组);
return root;
}

此时应该注意确定切割的标准，是左闭右开，还有左开又闭，还是左闭又闭，这个就是不变量，要在递归中保持这个不变量。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 第一步
        if (preorder.size() == 0) return NULL;
        // 第二步：前序遍历数组第一个元素，就是当前的中间节点
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);
        // 叶子节点
        if (preorder.size() == 1) return root;
        // 第三步：找切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size();
        delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 第四步：切割中序数组，得到中序左数组和中序右数组
        vector<int> leftInorder(inorder.begin(), inorder.begin() +
delimiterIndex);
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1,
inorder.end() );
        // 第五步：切割前序数组，得到前序左数组和前序右数组
        vector<int>::iterator it = preorder.begin();
        preorder.erase(it);
        vector<int> leftPreorder(preorder.begin(), preorder.begin()
+ leftInorder.size());
        vector<int> rightPreorder(preorder.begin() +
leftInorder.size(), preorder.end());
        // 第六步
        root->left = buildTree(leftPreorder, leftInorder);
        root->right = buildTree(rightPreorder, rightInorder);
        return root;
    }
};

这个代码性能并不好，因为代码里每层递归都定义了新的vector，既耗时又耗空间
可以用索引的方式重新写这个代码

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder,int preorderBegin,int preorderEnd, vector<int>& inorder,int inorderBegin,int inorderEnd){
        // 第一步
        if (preorderBegin >= preorderEnd) return NULL;
        // 第二步：前序遍历数组第一个元素，就是当前的中间节点
        int rootValue = preorder[preorderBegin];
        TreeNode* root = new TreeNode(rootValue);
        // 叶子节点
        if (preorderEnd - preorderBegin == 1) return root;
        // 第三步：找切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size();
        delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 第四步：切割中序数组，得到中序左数组和中序右数组
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;
        // 第五步：切割前序数组，得到前序左数组和前序右数组
        int leftPreorderBegin = preorderBegin+1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex -
inorderBegin;
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex -
inorderBegin);
 int rightPreorderEnd = preorderEnd;
        // 第六步
        root->left = traversal(preorder,leftPreorderBegin,leftPreorderEnd, inorder,leftInorderBegin,leftInorderEnd);
        root->right = traversal(preorder,rightPreorderBegin,rightPreorderEnd, inorder,rightInorderBegin,rightInorderEnd);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return NULL;
        TreeNode* node=traversal(preorder,0,preorder.size(),inorder,0,inorder.size());
        return node;
    }
};

106.从中序与后序遍历序列构造二叉树

和上道题类似，用后序的最后一个节点分割中序序列

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* traversal(vector<int>& inorder,int inorderBegin,int inorderEnd,vector<int>& postorder,int postorderBegin,int postorderEnd){
        // 第一步
        if (postorderBegin >= postorderEnd) return NULL;
        // 第二步：后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue = postorder[postorderEnd-1];
        TreeNode* root = new TreeNode(rootValue);
        // 叶子节点
        if (postorderEnd - postorderBegin == 1) return root;
        // 第三步：找切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size();
        delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 第四步：切割中序数组，得到中序左数组和中序右数组
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;
        // 第五步：切割后序数组，得到后序左数组和后序右数组
        int leftPostorderBegin = postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex -
inorderBegin;
        int rightPostorderBegin = postorderBegin + (delimiterIndex -
inorderBegin);
 int rightPostorderEnd = postorderEnd-1;
        // 第六步
        root->left = traversal(inorder,leftInorderBegin,leftInorderEnd, postorder,leftPostorderBegin,leftPostorderEnd);
        root->right = traversal(inorder,rightInorderBegin,rightInorderEnd, postorder,rightPostorderBegin,rightPostorderEnd);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0)
            return NULL;
        TreeNode* node = traversal(inorder,0,inorder.size(),postorder,0,postorder.size());
        return node;
    }
};