二叉树的根节点
双向链表的其中一个头节点。
{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
树的形状如上图 
中序遍历即可。只需要记录一个pre指针即可。
高分答案也太绕了吧
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree == nullptr) return nullptr;
TreeNode* pre = nullptr;
convertHelper(pRootOfTree, pre);
TreeNode* res = pRootOfTree;
while(res ->left)
res = res ->left;
return res;
}
void convertHelper(TreeNode* cur, TreeNode*& pre)
{
if(cur == nullptr) return;
convertHelper(cur ->left, pre);
cur ->left = pre;
if(pre) pre ->right = cur;
pre = cur;
convertHelper(cur ->right, pre);
}
};
class Solution {
public:
void ConverCore(TreeNode* pCurrent, TreeNode* &pLast)
{
if (!pCurrent)return;
ConverCore(pCurrent->left, pLast);
/*下面几句是最核心的同剑指offer思想一致
cur ->left = pre;
if(pre) pre ->right = cur;
pre = cur;*******/
if (!pLast)pCurrent->left = nullptr;//这句其实就是链表第一个点
else
{
pCurrent->left = pLast;
pLast->right = pCurrent;
}
pLast = pCurrent;
//********
ConverCore(pCurrent->right, pLast);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if (!pRootOfTree)return nullptr;
TreeNode* pLast = nullptr;
ConverCore(pRootOfTree, pLast);
TreeNode *pHead = nullptr;
while (pLast->left)
pLast = pLast->left;
pHead = pLast;
return pHead;
}
};
本地调试版
#include <iostream>
using namespace std;
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode() {}
};
TreeNode* newTree()
{
TreeNode* node = new TreeNode;
int x;
cin >> x;
if (!x)node = NULL;
else
{
node->val = x;
node->left = newTree();
node->right = newTree();
}
return node;
}
TreeNode* leftHead = NULL;
TreeNode* rightHead = NULL;
TreeNode* Convert(TreeNode* pRootOfTree)
{
if (pRootOfTree == NULL) return NULL;
Convert(pRootOfTree->left);
if (rightHead == NULL)
leftHead = rightHead = pRootOfTree;
else
{
rightHead->right = pRootOfTree;
pRootOfTree->left = rightHead;
rightHead = pRootOfTree;
}
Convert(pRootOfTree->right);
return leftHead;
}
void print(TreeNode* node)
{
while (node)
{
cout << node->val << " ";
node = node->right;
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
TreeNode* pRoot = NULL;
pRoot = newTree();
print(Convert(pRoot));
return 0;
}
class Solution:
"""使用辅助栈，中序遍历"""
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return
stack = []
p = pRootOfTree
pre = None
is_first = True
root = None
while stack or p:
while p:
stack.append(p)
p = p.left
p = stack.pop()
if is_first:
root = p
pre = root
is_first = False
else:
pre.right = p
p.left = pre
pre = p
p = p.right
return root
class Solution:
"""递归，使用辅助实例属性first"""
flag = 0
first = None
pre = None
def Convert(self, pRootOfTree):
# write code here
root = pRootOfTree
if not pRootOfTree:
return
self.Convert(root.left)
if not self.flag:
self.first = root
self.pre = self.first
self.flag = 1
else:
self.pre.right = root
root.left = self.pre
self.pre = root
self.Convert(root.right)
return self.first
class Solution:
"""不借助实例属性递归"""
def Convert(self, pRootOfTree):
# write code here
root = pRootOfTree
if not root:
return
pre = None
self.inorder(pRootOfTree, pre)
while root.left:
root = root.left
return root
def inorder(self, current, pre):
if not current:
return pre
pre = self.inorder(current.left, pre)
current.left = pre
if pre:
pre.right = current
pre = current
return self.inorder(current.right, pre)
python的三种实现方式
class Solution {
public:
TreeNode* Convert(TreeNode* p)
{
if(p==0) return 0;
if(p->left)
{
TreeNode* p0=Convert(p->left);
while(p0->right!=0)
p0=p0->right;
p->left=p0;
p0->right=p;
}
if(p->right)
{
TreeNode* p1=Convert(p->right);
p->right=p1;
p1->left=p;
}
while(p->left!=0)
p=p->left;
return p;
}
};
public class Solution {
public TreeNode Convert(TreeNode root) {
if(root==null)
return null;
get(root);
while(root.left!=null)
root = root.left;
return root;
}
public TreeNode get(TreeNode root) {
if(root.left!=null){
TreeNode pre = get(root.left);
while(pre.right!=null)
pre = pre.right;
pre.right = root;
root.left = pre;
}
if(root.right!=null){
TreeNode next = get(root.right);
while(next.left!=null)
next = next.left;
next.left = root;
root.right = next;
}
return root;
}
}
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
//直接用中序遍历
public class Solution {
TreeNode head = null;
TreeNode realHead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}
private void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left);
if (head == null) {
head = pRootOfTree;
realHead = pRootOfTree;
} else {
head.right = pRootOfTree;
pRootOfTree.left = head;
head = pRootOfTree;
}
ConvertSub(pRootOfTree.right);
}
}
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
// 双向链表左头节点
private TreeNode leftHead;
// 双向链表右头节点
private TreeNode rightHead;
public TreeNode Convert(TreeNode pRootOfTree) {
// base case 节点为空时，返回 null
if (pRootOfTree == null) {
return null;
}
// 先将节点左子树进行转换
Convert(pRootOfTree.left);
// 若此时左头节点为空，则将左右头节点均设置为当前节点
if (leftHead == null) {
leftHead = pRootOfTree;
rightHead = pRootOfTree;
} else {
// 否则，将当前节点与右头节点连接，并更新右头节点
rightHead.right = pRootOfTree;
pRootOfTree.left = rightHead;
rightHead = pRootOfTree;
}
// 将节点右子树进行转换
Convert(pRootOfTree.right);
// 返回左头节点
return leftHead;
}
}
class Solution: def Convert(self, pRootOfTree): # write code here if not pRootOfTree: return None self.list = [] self.midTree(pRootOfTree) if len(self.list)==1: return self.list[0] for i, node in enumerate(self.list): if i != len(self.list) - 1: node.right = self.list[i + 1] self.list[i + 1].left = node else: node.left = self.list[i - 1] return self.list[0] def midTree(self, root): if not root: return self.midTree(root.left) self.list.append(root) self.midTree(root.right)
public class Solution {
TreeNode head, pre;
public TreeNode Convert(TreeNode pRootOfTree) {
//中序遍历，在访问每个节点时构建cur和前驱节点pre的引用指向
if(pRootOfTree == null) return null;
dfs(pRootOfTree);
return head;
}
void dfs(TreeNode cur) {
if(cur == null) return ;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: pre = None head = None def Convert(self, pRootOfTree): # write code here # 中序遍历时改变指向 self.pre = None self.head = None def midorder(node): if node is None: return None midorder(node.left) if not self.pre: self.pre = node self.head = node node.left = None else: self.pre.right = node node.left = self.pre self.pre = node midorder(node.right) midorder(pRootOfTree) return self.head
class Solution: def Convert(self , pRootOfTree ): self.pre = None def dfs(root, pre): if root.left: dfs(root.left, self.pre) if self.pre is None: head.left = root root.left = None else: root.left = self.pre self.pre.right = root self.pre = root if root.right: self.pre.right = root.right dfs(root.right, self.pre) if pRootOfTree is None: return None head = TreeLinkNode(-1) dfs(pRootOfTree, self.pre) return head.leftpre指针必须为全局变量
class Solution {
public:
TreeNode* head = new TreeNode(-1);
TreeNode* pre = head;
TreeNode* Convert(TreeNode* pRootOfTree) {
if(!pRootOfTree) return nullptr;
dfs(pRootOfTree);
//head->left = nullptr;
head->right->left = nullptr;
return head->right;
}
void dfs(TreeNode* root){
if(!root) return ;
dfs(root->left);
pre->right = root;
root->left = pre;
pre = root;
dfs(root->right);
}
}; 
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
//二叉搜索树的中序遍历是排序的
if (pRootOfTree == null) {
return null;
}
//将二叉搜索树转换成一个双向链表
inOrderConvert(pRootOfTree);
//别忘了原来的根节点可不是现在的双向链表的头结点！赶快移过去！
TreeNode head = pRootOfTree;
while (head.left != null){
head = head.left;
}
return head;
}
TreeNode prev = null;//记录当前已经修改的节点
public void inOrderConvert(TreeNode root){
if (root == null){
return;
}
inOrderConvert(root.left);
//要想将其转化为双向链表，只需在中序遍历的过程中修改left和right的指向
//left -> 双向链表的前驱 prev
//right -> 双向链表的后继 next
root.left = prev;
if (prev != null){
//第一个不需要，否则null.right会报空指针异常
prev.right = root;
}
prev = root;
inOrderConvert(root.right);
}
} 
public class Solution {
TreeNode pre = null;
TreeNode ans = null;
public TreeNode Convert(TreeNode root) {
if (root == null) return ans;
Convert(root.left);
if (ans == null) {
//中序遍历下最左边的一个是头
ans = root;
} else {
pre.right = root;
root.left = pre;
}
pre = root;
Convert(root.right);
return ans;
}
} 
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode pre = null;
TreeNode head = null;
public TreeNode Convert(TreeNode pRootOfTree) {
process(pRootOfTree);
return head;
}
public void process(TreeNode root) {
if (root == null) {
return;
}
process(root.left);
if (head == null) {
head = root;
} else {
root.left = pre;
pre.right = root;
}
pre = root;
process(root.right);
}
}
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode *last, *sta;
void Dfs(TreeNode *rt)
{
if (rt == NULL) return;
Dfs(rt->left);
if (last != nullptr) {
last->right = rt;
rt->left = last;
}
if (last == nullptr) sta = rt;
last = rt;
Dfs(rt->right);
}
TreeNode* Convert(TreeNode* pRoot) {
if (pRoot == NULL) return NULL;
last = nullptr;
Dfs(pRoot);
return sta;
}
}; 
class Solution {
public:
// 递归方法，只要知道二叉搜索树的最小节点在最左面，最大节点在最右面
// 每次把左子树的最大节点以及右子树的最小节点与根相连即可
void recur(TreeNode * p) {
TreeNode *q;
// 递归终止条件：左右子树均为空
if(p->left) {
q = p->left;
// 寻找左子树的最大节点
while(q->right)
q = q->right;
// 这里注意先递归再连接节点
recur(p->left);
q->right = p;
p->left = q;
}
// 右子树的操作同理
if(p->right) {
q = p->right;
while(q->left)
q = q->left;
recur(p->right);
q->left = p;
p->right = q;
}
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
// 特判
if(!pRootOfTree) return NULL;
// 返回整棵树的最小值也就是最左值
TreeNode *res = pRootOfTree;
while(res->left)
res = res->left;
// 递归转为双向链表
recur(pRootOfTree);
return res;
}
}; 
扫描二维码，关注牛客网
下载牛客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; }