二叉树的根节点
双向链表的其中一个头节点。
{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
树的形状如上图 
TreeNode pre=new TreeNode(0) ,p1=pre;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
dfs(pRootOfTree);
pre.right.left=null; // 避免把pre节点算进去
return pre.right;
}
public void dfs(TreeNode pRoot){
if(pRoot==null){
return;
}
dfs(pRoot.left);
// 中序遍历，依次进行节点连接，p1向右传递
pRoot.left=p1;
p1.right=pRoot;
p1=p1.right;
dfs(pRoot.right);
} public class Solution {
private TreeNode pre = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (null == pRootOfTree) {
return null;
}
inorder(pRootOfTree);
TreeNode head = pRootOfTree;
while (head.left != null) {
head = head.left;
}
return head;
}
private void inorder(TreeNode root) {
if (null == root) {
return ;
}
inorder(root.left);
if (pre != null) {
pre.right = root;
root.left = pre;
}
pre = root;
inorder(root.right);
}
} 
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode res = null;
TreeNode pre = null;
public TreeNode Convert(TreeNode pRootOfTree) {
midOrder(pRootOfTree);
return res;
}
public void midOrder(TreeNode root) {
if(root != null) {
midOrder(root.left);
if(res == null) {
res = root;
pre = root;
} else {
pre.right = root;
root.left = pre;
pre = root;
}
midOrder(root.right);
}
}
}
import java.util.*;
/**
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;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) return null;
InOrder(pRootOfTree);
TreeNode p = pRootOfTree;
while (p.left != null) {
p = p.left;
}
return p;
}
public void InOrder(TreeNode Root) {
if (Root == null) {
return;
}
InOrder(Root.left);
Root.left = pre;
if (pre != null) {
pre.right = Root;
}
pre = Root;
InOrder(Root.right);
}
}
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode prev = null;
public void convertChild(TreeNode pCur) {
if(pCur == null) {
return;
}
convertChild(pCur.left);
pCur.left = prev;
if(prev != null) {
prev.right = pCur;
}
prev = pCur;
convertChild(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
convertChild(pRootOfTree);
TreeNode head = pRootOfTree;
while(head.left != null) {
head = head.left;
}
return head;
}
}
public class Solution {
TreeNode head=null;//赋初值为null
TreeNode pre=null;
//双向链表必然要定义head、pre
public TreeNode Convert(TreeNode pRootOfTree) {
build(pRootOfTree);
return head;
}
public void build(TreeNode root){
//必然是中序遍历
if(root==null) return ;
build(root.left);
if(pre==null){
pre=root;
head=root;
}else{
pre.right=root;//这里head、pre定义为TreeNode 所以这里是pre.right head.left
root.left=pre;//root来回倒
pre=root;
}
build(root.right);
} 
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode pre=null;
public TreeNode head=null;
public TreeNode Convert(TreeNode root) {
//如果根节点为空则为空
if(root==null){
return null;
}
//用来保存创建的双向链表
ArrayList<TreeNode> tree=new ArrayList<>();
//中序遍历
mid(root,tree);
//清空tree节点每个左右分支
for(int i=0;i<tree.size();i++){
TreeNode tmp=tree.get(i);
tmp.left=null;
tmp.right=null;
}
//开始构建从左到右单向链表
for(int i=0;i<tree.size()-1;i++){
TreeNode tmp=tree.get(i);
tmp.right=tree.get(i+1);
}
//开始构建从右到左的单向链表
for(int i=tree.size()-1;i>0;i--){
TreeNode tmp=tree.get(i);
tmp.left=tree.get(i-1);
}
//返回第一个tree节点，就是双向链表的头节点
return tree.get(0);
}
public void mid(TreeNode root,ArrayList<TreeNode> tree){
if(root==null){
return;
}
mid(root.left,tree);
tree.add(root);
mid(root.right,tree);
}
}
这叫排好序? 
public TreeNode hair = new TreeNode(-1);
public TreeNode temp = hair;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
convertSub(pRootOfTree);
hair.right.left = null;
return hair.right;
}
public void convertSub(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return;
}
convertSub(pRootOfTree.left);
temp.right = pRootOfTree;
pRootOfTree.left = temp;
temp = pRootOfTree;
convertSub(pRootOfTree.right);
} 
public class Solution {
boolean isLeaf(TreeNode root){
if(root==null)return false;
if(root.left==null&&root.right==null)return true;
return false;
}
TreeNode doi(TreeNode root, int flag){
System.out.println("root:"+root.val+"flag:"+flag);
if(flag==0&&isLeaf(root.left)){
root.left.right=root;
return root.left;
}
if(flag==1&&isLeaf(root.right)){
root.right.left=root;
return root.right;
}
if(flag==0&&root.left==null)return root;
else if(flag==0&&root.left!=null){
TreeNode left=root.left;
TreeNode res=doi(left,0);
TreeNode pre=doi(left,1);
root.left=pre;pre.right=root;
return res;
}
if(flag==1&&root.right==null)return root;
else if(flag==1&&root.right!=null){
TreeNode right=root.right;
TreeNode bac=doi(right,0);
TreeNode res=doi(right,1);
root.right=bac;bac.left=root;
return res;
}
return null;
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)return null;
if(isLeaf(pRootOfTree))return pRootOfTree;
TreeNode res=doi(pRootOfTree,0);
doi(pRootOfTree,1);
return res;
}
} 
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
List<TreeNode> list = new ArrayList<>();
traveMid(pRootOfTree, list);
// 根据数组重建双向链表
for (int i=0; i<list.size()-1; i++) {
TreeNode p = (TreeNode)list.get(i);
TreeNode q = (TreeNode)list.get(i+1);
p.right = q;
q.left = p;
}
return list.isEmpty() ? null : (TreeNode)list.get(0);
}
private void traveMid(TreeNode node, List<TreeNode> list) {
if (node == null) {
return;
}
traveMid(node.left, list);
list.add(node);
traveMid(node.right, list);
}
} 
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private TreeNode prev;
private TreeNode head;
private TreeNode leftLast;
public TreeNode Convert(TreeNode root) {
if (root == null) {
return null;
}
// doConvert(root);
// return head;
return convert3(root);
}
//方法3 非递归-栈
private TreeNode convert3(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
boolean isFirst = true;
TreeNode prev = null;
while(p != null || !stack.isEmpty()) {
while(p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if (isFirst) {
root = p;
prev = p;
isFirst = false;
}else {
prev.right = p;
p.left = prev;
prev = p;
}
p = p.right;
}
return root;
}
//方法2
private TreeNode convert2(TreeNode root) {
if (root == null) {
return null;
}
if (root.left == null && root.right == null) {
leftLast = root;
return root;
}
TreeNode left = convert2(root.left);
if (left != null) {
leftLast.right = root;
root.right = leftLast;
}
TreeNode right = convert2(root.right);
if (right != null) {
right.left = root;
root.right = right;
}
return left != null ? left : right;
}
//方法1--递归
private void doConvert(TreeNode root) {
if (root == null) {
return;
}
doConvert(root.left);
if (prev == null) {
prev = root;
head = root;
} else {
root.left = prev;
prev.right = root;
prev = root;
}
doConvert(root.right);
}
}
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode root) {
if(root==null) return null;
List<TreeNode> t = new ArrayList();
bfs(root,t);
TreeNode pre = null;
for(int i=0,max = t.size()-1;i<max;i++){
t.get(i).left = pre;
t.get(i).right = t.get(i+1);
pre = t.get(i);
}
t.get(t.size()-1).left = pre;
return t.get(0);
}
public void bfs(TreeNode root,List list){
if(null!=root){
if(null!=root.left)bfs(root.left,list);
list.add(root);
if(null!=root.right)bfs(root.right,list);
}
}
} 
扫描二维码，关注牛客网
下载牛客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; }