C++刷题之旅（42）

数组的元素已经升序排好，每次寻找数组中点，分为左右区间，即左右子节点。

class Solution {
public:
    TreeNode* traversal(vector nums, int left, int right){
        if(left > right) 
            return nullptr;

        int mid = left + ((right - left) / 2);    //取中点
        TreeNode* root = new TreeNode(nums[mid]);  //创建节点
        root->left = traversal(nums, left, mid-1);  //更新左节点
        root->right = traversal(nums, mid+1, right);    //更新右节点
        return root;
    }

    TreeNode* sortedArrayToBST(vector& nums) {
       TreeNode* root = traversal(nums, 0, nums.size()-1);
       return root;
    }
};

前序遍历形式：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
中序遍历形式：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
根节点总是前序遍历中的第一个节点，只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目，左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

class Solution {
public:

    unordered_map pos;
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++)
            pos[inorder[i]] = i; //记录中序遍历的根节点位置
        return dfs(preorder,inorder,0,n-1,0,n-1);        
    }
    //pl,pr对应一棵子树的先序遍历区间的左右端点
    //il,ir对应一棵子树的中序遍历区间的左右端点
    TreeNode* dfs(vector&pre,vector&in,int pl,int pr,int il,int ir)
    {
        if(pl > pr || il > ir)  return NULL; //子树为空
        int k = pos[pre[pl]] - il; // pos[pre[pl]]是中序遍历中根节点位置，k是子树先序和中序遍历的长度
        TreeNode* root = new TreeNode(pre[pl]);
         // 先序遍历中「从 左边界+1 开始到左子树节点数目的元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
         // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->left = dfs(pre,in,pl+1,pl+k,il,il+k-1);  //左子树前序遍历，左子树中序遍历
        root->right = dfs(pre,in,pl+k+1,pr,il+k+1,ir); //右子树前序遍历，右子树中序遍历
        return root;
    }
};

先从左到右，在从右到左，利用双端队列来控制当层节点值输出的顺序。

class Solution {
public:
    vector> zigzagLevelOrder(TreeNode* root) {
        vector> ans;
        if(!root) return ans;
        bool left_flag = true;    //是否从左往右遍历的标志
        queue que;    
        que.push(*root);    
        while(!que.empty()){
            deque dlist;   //定义一个双端队列储存当前层的值，方便调换方向， 局部变量
            int n = que.size();   //当前层节点的个数
            for(int i = 0; i < n; i++){
                auto node = que.front();   //取节点
                que.pop();
                if(left_flag){
                    dlist.push_back(node.val);   //存入顺序和读取下一层顺序一致
                }else{
                    dlist.push_front(node.val);  //反向存入，即反向遍历
                }
                //将下一层的节点入队
                if(node.left) que.push(*node.left);
                if(node.right) que.push(*node.right);
            }
            ans.push_back(vector{dlist.begin(), dlist.end()});  //每遍历完一层，压入到ans中
            left_flag = !left_flag;   //遍历完一层，标志位转换
        }
        return ans;
    }
};