本文共 4004 字，大约阅读时间需要 13 分钟。
1、二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求值的顺序保持不变，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。返回转换后的单向链表的头节点。示例：输入： [4,2,5,1,3,null,6,0]输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]提示：节点数量不会超过 100000。
思路：
二叉搜索树的层序遍历/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution { public: TreeNode* pointer = new TreeNode(0); TreeNode* pointer2 = pointer; TreeNode* convertBiNode(TreeNode* root) { dfs(root); return pointer2->right; } void dfs(TreeNode* root) { if (root != NULL) { dfs(root->left); visit(root); //Visit the current node dfs(root->right); } } void visit(TreeNode* root) { root->left = NULL; pointer->right = root; pointer = root; }}; 问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]…a[n]。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格式第一行一个整数n。下面每行，一个数x。如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，表示这个节点是叶子节点，权值为x。输出格式输出一个整数，表示最少有多少逆序对。样例输入300312样例输出1数据规模与约定对于20%的数据，n <= 5000。对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。
cpoy的代码，看不懂
#include#include using namespace std;#define ForD(i,n) for(int i=n;i;i--)#define F (100000007)#define MAXN (2*200000+10)long long mul(long long a,long long b){ return (a*b)%F;}long long add(long long a,long long b){ return (a+b)%F;}long long sub(long long a,long long b){ return (a-b+(a-b)/F*F+F)%F;}int n,root=0;/*n->叶子结点数,root->根序号？*/struct node{ int fa; /*父结点的下标*/ int ch[2]; /*0->左树下标 1->右树下标*/ int size; /*size->当前结点含有的有效结点数*/ int c; /*当前结点的数值*/ node():size(0),c(0){ ch[0]=ch[1]=fa=0;} /*初始化为0*/}a[MAXN]; /*树形数组->纪录各叶结点的数值*/void update(int x)/*更新叶结点个数*/{ a[x].size=a[a[x].ch[0]].size+a[a[x].ch[1]].size+(a[x].c>0);}int tail=0;void pushdown(int x)/*将叶结点的父结点指向当前结点*/{ a[a[x].ch[0]].fa=a[a[x].ch[1]].fa=x;}/*创建树*/void build(int &x){ if (!x) x=++tail; scanf("%d",&a[x].c); if (a[x].c==0) { build(a[x].ch[0]);/*创建左子树*/ build(a[x].ch[1]);/*创建右子树*/ update(x);pushdown(x);/*更新当前结点的有效叶结点个数，以及父结点指向*/ }else a[x].size=1;}void rotate(int x)/*旋转*/{ int y=a[x].fa,z=a[y].fa; bool p=a[y].ch[0]==x; if (z) /*有爷爷*/ { if (a[z].ch[0]==y) /*未旋转*/ a[z].ch[0]=x;/*将子树提拔为父树(升序)*/ else a[z].ch[1]=x; /*还原状态*/ } a[x].fa=z,a[y].fa=x;/*当前结点与父结点交换(父结点指向)*/ if (a[x].ch[p]) /*原子树是否有右树(隔代转移)*/ a[a[x].ch[p]].fa=y; a[y].ch[p^1]=a[x].ch[p]; a[x].ch[p]=y; /*父树移至子树的右端(右树)*/ update(y); /*更新旋转后，子树的结点的有效结点数*/}void splay(int x){ while (a[x].fa)/*不为根结点*/ { int y=a[x].fa,z=a[y].fa; if (z) /*有爷爷*/ if ((a[y].ch[0]==x)^(a[z].ch[0]==y)) rotate(x);/*旋转*/ else rotate(y); rotate(x); } update(x);}void ins(long long &tot,int x,int y){ a[x].size++; /*插入+1*/ if (a[y].c<=a[x].c) /*是逆序对*/ { if (a[x].ch[0]) /*左树有子*/ ins(tot,a[x].ch[0],y); else /*左树无子*/ a[y].fa=x,splay(a[x].ch[0]=y);/*右数插入到左树子*/ } else { tot+=a[a[x].ch[0]].size+(a[x].c>0); if (a[x].ch[1]) ins(tot,a[x].ch[1],y); else a[y].fa=x,splay(a[x].ch[1]=y); }}int q[MAXN],size;void clac(int x,int y){ if (a[y].ch[0]) clac(x,a[y].ch[0]); if (a[y].c) q[++size]=y; if (a[y].ch[1]) clac(x,a[y].ch[1]);}long long merge(bool &lor,int z)/*分治*/{ int x=a[z].ch[0],y=a[z].ch[1]; if (a[x].size
转载地址：http://hwgwi.baihongyu.com/