二叉树的根节点
双向链表的其中一个头节点。
{10,6,14,4,8,12,16}From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
{5,4,#,3,#,2,#,1}From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
5
/
4
/
3
/
2
/
1
树的形状如上图 
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
struct TreeNode *LeftTreeNode, *RootTreeNode, *RightTreeNode, *res;
if(pRootOfTree==NULL)
return NULL;
RootTreeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
RootTreeNode->val = pRootOfTree->val;
RootTreeNode->left = NULL;
RootTreeNode->right = NULL;
res = RootTreeNode;
if(pRootOfTree->left) {
struct TreeNode *p;
LeftTreeNode = Convert(pRootOfTree->left);
p = LeftTreeNode;
while(p->right!=NULL)
p = p->right;
p->right = RootTreeNode;
RootTreeNode->left = p;
res = LeftTreeNode;
}
if(pRootOfTree->right) {
RightTreeNode = Convert(pRootOfTree->right);
RightTreeNode->left = RootTreeNode;
RootTreeNode->right = RightTreeNode;
}
return res;
} 
struct TreeNode* deep(struct TreeNode* root, struct TreeNode* now){
if(now==NULL){
return NULL;
}
now->left = deep(now,now->left);
now->right = deep(now,now->right);
struct TreeNode* tmp;
tmp = now;
if(root==NULL){
while(tmp->left!=NULL){
tmp = tmp->left;
}
return tmp;
}
if(now->val < root->val){
while(tmp->right!=NULL){
tmp = tmp->right;
}
tmp->right = root;
}else{
while(tmp->left!=NULL){
tmp = tmp->left;
}
tmp->left = root;
}
return tmp;
}
struct TreeNode* Convert(struct TreeNode* root ) {
return deep(NULL,root);
} 
static struct TreeNode *pre;
void InOrder(struct TreeNode *t){
if(t==NULL)return ;
InOrder(t->left);
//调整指向
t->left=pre;
if(pre!=NULL){
pre->right=t;
}
pre=t;
InOrder(t->right);
}
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
// write code here
if(pRootOfTree==NULL)return pRootOfTree;
struct TreeNode *p=pRootOfTree,*pre=NULL;
while(p->left!=NULL) p=p->left;//起点
InOrder(pRootOfTree);
return p;
} 
typedef struct TreeNode* tLink;
tLink solve(struct TreeNode* root, int flag){
if(root){
tLink pre = solve(root->left, 0);
tLink suc = solve(root->right, 1);
// 把修改的结点的任务交给parent
if(pre)
root->left = pre, pre->right = root;
if(suc)
root->right = suc, suc->left = root;
if(flag == 0){
while(root->right)
root = root->right;
}else{
while(root->left)
root = root->left;
}
return root;
}
return NULL;
}
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
// write code here
return solve(pRootOfTree, 1);
}
typedef struct TreeNode* PTreeNode;
void traverse(PTreeNode root, PTreeNode* pre) {
if (!root) return;
traverse(root->right, pre);
root->right = *pre;
*pre = *pre ? (*pre)->left = root : root;
traverse(root->left, pre);
}
/**
*
* @param pRootOfTree TreeNode类
* @return TreeNode类
*/
PTreeNode Convert(PTreeNode pRootOfTree) {
PTreeNode pre = NULL;
traverse(pRootOfTree, &pre);
return pre;
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
方法一：非递归版 解题思路： 1.核心是中序遍历的非递归算法。 2.修改当前遍历节点与前一遍历节点的指针指向。 import java.util.Stack; public TreeNode ConvertBSTToBiList(TreeNode root) { if(root==null) return null; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; TreeNode pre = null;// 用于保存中序遍历序列的上一节点 boolean isFirst = true; while(p!=null||!stack.isEmpty()){ while(p!=null){ stack.push(p); p = p.left; } p = stack.pop(); if(isFirst){ root = p;// 将中序遍历序列中的第一个节点记为root pre = root; isFirst = false; }else{ pre.right = p; p.left = pre; pre = p; } p = p.right; } return root; } 方法二：递归版 解题思路： 1.将左子树构造成双链表，并返回链表头节点。 2.定位至左子树双链表最后一个节点。 3.如果左子树链表不为空的话，将当前root追加到左子树链表。 4.将右子树构造成双链表，并返回链表头节点。 5.如果右子树链表不为空的话，将该链表追加到root节点之后。 6.根据左子树链表是否为空确定返回的节点。 public TreeNode Convert(TreeNode root) { if(root==null) return null; if(root.left==null&&root.right==null) return root; // 1.将左子树构造成双链表，并返回链表头节点 TreeNode left = Convert(root.left); TreeNode p = left; // 2.定位至左子树双链表最后一个节点 while(p!=null&&p.right!=null){ p = p.right; } // 3.如果左子树链表不为空的话，将当前root追加到左子树链表 if(left!=null){ p.right = root; root.left = p; } // 4.将右子树构造成双链表，并返回链表头节点 TreeNode right = Convert(root.right); // 5.如果右子树链表不为空的话，将该链表追加到root节点之后 if(right!=null){ right.left = root; root.right = right; } return left!=null?left:root; } 方法三：改进递归版 解题思路： 思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。 // 记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点 protected TreeNode leftLast = null; public TreeNode Convert(TreeNode root) { if(root==null) return null; if(root.left==null&&root.right==null){ leftLast = root;// 最后的一个节点可能为最右侧的叶节点 return root; } // 1.将左子树构造成双链表，并返回链表头节点 TreeNode left = Convert(root.left); // 3.如果左子树链表不为空的话，将当前root追加到左子树链表 if(left!=null){ leftLast.right = root; root.left = leftLast; } leftLast = root;// 当根节点只含左子树时，则该根节点为最后一个节点 // 4.将右子树构造成双链表，并返回链表头节点 TreeNode right = Convert(root.right); // 5.如果右子树链表不为空的话，将该链表追加到root节点之后 if(right!=null){ right.left = root; root.right = right; } return left!=null?left:root; }