网站banner flash源文件/常州网络推广seo

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：

二叉搜索树，左节点<根节点<右节点

中序遍历即为 从小到大的递增序列

struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

核心函数：Convert

采用递归的思路

递归的进入左右子树

递归返回条件：到达叶子节点

先将左右子树的调整好的递增序列返回后

重构双向链接

注意点：返回的双向链表的Head节点，所以在重构序列时需要滑动到边界处

 TreeNode* Convert(TreeNode* pRootOfTree){if(pRootOfTree==NULL)return NULL;if(pRootOfTree->left==NULL && pRootOfTree->right==NULL)return pRootOfTree;TreeNode* myleft=pRootOfTree->left;TreeNode* myRight=pRootOfTree->right;TreeNode* theleft=NULL;TreeNode* theright=NULL;if(pRootOfTree->left!=NULL)theleft=Convert(pRootOfTree->left);TreeNode* templeft=theleft;if(templeft!=NULL){while(templeft->right!=NULL)templeft=templeft->right;templeft->right=pRootOfTree;pRootOfTree->left=templeft;}if(pRootOfTree->right!=NULL)theright=Convert(pRootOfTree->right);TreeNode* tempright=theright;if(tempright!=NULL){while(tempright->left!=NULL)tempright=tempright->left;tempright->left=pRootOfTree;pRootOfTree->right=tempright;}if(theleft==NULL)return pRootOfTree;elsereturn theleft;}