首页 > 试题广场 >

二叉搜索树与双向链表

[编程题]二叉搜索树与双向链表
  • 热度指数：626299 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示


数据范围：输入二叉树的节点数 ，二叉树中每个节点的值
要求：空间复杂度（即在原树上操作），时间复杂度

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述:
二叉树的根节点


输出描述:
双向链表的其中一个头节点。
示例1

输入

{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;

说明

输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2

输入

{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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
nailperry头像 nailperry 
方法一：非递归版
解题思路：
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;        
    }

编辑于 2015-08-18 23:36:07 回复(111)
Python
木有粗面201904101731812头像 木有粗面201904101731812 
# 直接递归，不添加额外变量
class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return None
        # 左子树需要返回最左侧的节点，右子树需要返回最右侧的节点
        def doConnect(leftNode, rightNode):
            leftNode.right = rightNode
            rightNode.left = leftNode
            
        def creatDul(pRootOfTree):
            if not pRootOfTree:
                return None, None
            _, rightNode = creatDul(pRootOfTree.left)
            leftNode, _ = creatDul(pRootOfTree.right)
            if rightNode:
                doConnect(rightNode, pRootOfTree)
            if leftNode:
                doConnect(pRootOfTree, leftNode)
            if not leftNode&nbs***bsp;not rightNode:
                return pRootOfTree, pRootOfTree
            else:
                return rightNode, leftNode
            
        creatDul(pRootOfTree)
        finalNode = pRootOfTree
        while finalNode.left != None:
            finalNode = finalNode.left
        return finalNode

发表于 2022-07-29 19:07:04 回复(0)
Python
Dinochang头像 Dinochang 
# -*- 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 

发表于 2022-04-08 19:58:39 回复(0)
Python
牛客824450号头像 牛客824450号
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree == None:
            return pRootOfTree
        stack = []
        temp = pRootOfTree
        f = False
        res,pre = None,None
        while temp:
            stack.append(temp)
            temp=temp.left
        while len(stack)>0:
            top=stack.pop()
            if not f:
                res = top
                pre= top
                f = True
            else:
                pre.right = top
                top.left = pre
                pre = top
            temp=top.right
            while temp:
                stack.append(temp)
                temp=temp.left
        return res
发表于 2021-09-08 09:19:15 回复(0)
Python
Hiroi头像 Hiroi
Python 用stack进行中序遍历 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree is None:
            return pRootOfTree
        else:
            stack = []
            head = None
            pre = head
            while pRootOfTree is not None&nbs***bsp;len(stack)>0:
                while pRootOfTree is not None:
                    stack.append(pRootOfTree)
                    pRootOfTree = pRootOfTree.left
                if len(stack)>0:
                    pRootOfTree = stack.pop()
                    if pre is None:
                        head = pRootOfTree
                    else:
                        pre.right = pRootOfTree
                    pRootOfTree.left = pre
                    pre = pRootOfTree
                    pRootOfTree = pRootOfTree.right
            return head


发表于 2021-04-17 20:49:17 回复(0)
Python
CrucioLzy头像 CrucioLzy
高赞答案硬是绕的我没太看懂  
class Solution:
    def Convert(self, pRoot):
        # write code here
        
        if pRoot == None:
            return
        Node = pRoot 
        stack = []
        p = None #记录一下前一个节点
        while stack&nbs***bsp;Node:
            while Node:
                stack.append(Node)
                Node = Node.left
            Node = stack.pop()
            if p == None:
                p = Node
            else:
                p.right = Node
                Node.left = p
                p = Node
            Node = Node.right
        while pRoot.left:
            pRoot = pRoot.left
        return pRoot
        


发表于 2020-08-02 13:54:39 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def Convert(self, root):
        #如果根为空，则返回空
        if not root:
            return None
        #如果此时的“根节点”的左子树和右子树同时为空，则返回“根节点”
        if not root.left and not root.right:
            return root
         
        # 将左子树构建成双链表，返回链表头
        left = self.Convert(root.left)
        p = left
         
        # 定位至左子树的最右的一个结点（注意不是最左子树的右节点，而是左子树的最右的节点）
        while left and p.right:
            p = p.right
        #如果左子树不为空，将当前root加到左子树链表
        if left:
            p.right = root
            root.left = p
        # 将右子树构造成双链表，返回链表头
        right = self.Convert(root.right)
        # 如果右子树不为空，将该链表追加到root结点之后
        if right:
            right.left = root
            root.right = right
             
        return left if left else root
这个题好费脑子。。。
发表于 2020-07-24 20:03:20 回复(0)
Python
sk8_wt头像 sk8_wt 
class Solution:
    def Convert(self, pRootOfTree):
        if not pRootOfTree:
            return pRootOfTree
        
        left = self.Convert(pRootOfTree.left)
        if left:
            while left.right:
                left = left.right
            left.right = pRootOfTree
            pRootOfTree.left = left
            
        right = self.Convert(pRootOfTree.right)
        if right:
            right.left = pRootOfTree
            pRootOfTree.right = right
            
        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left
        return pRootOfTree

发表于 2020-07-17 16:25:14 回复(0)
Python
西二旗小王头像 西二旗小王
非递归中序遍历，设置pre指针，第一次给pre赋值时，用re指向链表头节点，把当前访问节点和pre所指的上一个节点联系起来，遍历完成输出链表头节点re。 

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        stack = []
        pre = None
        while stack&nbs***bsp;pRootOfTree:
            while pRootOfTree:
                stack.append(pRootOfTree)
                pRootOfTree = pRootOfTree.left
            pRootOfTree = stack.pop(-1)
            if pre:
                pre.right = pRootOfTree
                pRootOfTree.left = pre
            else:
                pRootOfTree.left = pre
                re = pRootOfTree
            pre = pRootOfTree
            pRootOfTree = pRootOfTree.right
        return re

编辑于 2020-04-25 21:42:01 回复(0)
Python
KIng兮头像 KIng兮
利用一个栈
从最右节点开始遍历，一个节点的前置节点不是直接连在它的根节点上，就是其根节点的左孩子的最右孩子（读起来可能绕口，稍微画下图即可理解）；一个节点的后置节点就是上一个遍历的点（保存在栈中，上一个被弹出的点） 
    def conserve(self,root):
        if root is None:return False
        s = []
        s.append(root)
        temp = None
        while root.right:
            root = root.right
            s.append(root)
        while s.__len__():
            t = s.pop()
            l = t.left
            if l:
                while l:
                    s.append(l)
                    l = l.right
                le = s.__len__() - 1
                if le >= 0:
                    t.left , t.right = s[le] , temp
                    temp = t
                else:
                    t.left , t.right = None , temp
                    temp = t
            else:
                le = s.__len__() - 1
                if le >= 0 :
                    t.left , t.right = s[le] , temp
                    temp = t
                else:
                    t.left , t.right = None , temp
                    temp = t


发表于 2020-04-10 17:43:05 回复(0)
Python
accer头像 accer 
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree == None:
            return None

        leftChild = leftMaxNode = pRootOfTree.left
        if pRootOfTree.left != None and (pRootOfTree.left).right != pRootOfTree:
            if leftMaxNode != None:
                while leftMaxNode.right != None:
                    leftMaxNode = leftMaxNode.right
            leftMaxNode.right = pRootOfTree
            pRootOfTree.left = leftMaxNode
            if leftChild.left != None:
                self.Convert(leftChild)

        rightChild = rightMinNode = pRootOfTree.right
        if pRootOfTree.right != None and (pRootOfTree.right).left != pRootOfTree:
            if rightMinNode != None:
                while rightMinNode.left != None:
                    rightMinNode = rightMinNode.left
            rightMinNode.left = pRootOfTree
            pRootOfTree.right = rightMinNode
            if rightChild.right != None:
                self.Convert(rightChild)

        while pRootOfTree.left != None:
            pRootOfTree = pRootOfTree.left
        return pRootOfTree

发表于 2020-03-22 11:06:13 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# 解体思路：递归实现中序遍历二叉搜索树
# 递归处理左子树，链接根节点与左子树最右节点；
# 递归处理右子树，链接根节点与右子树最左节点
# 向前遍历到第一个节点，返回节点地址
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None

        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree

        # 递归处理左子树
        self.Convert(pRootOfTree.left)
        left = pRootOfTree.left

        # 将根节点左指针指向左子树最右孩子，左子树最右孩子的右指针指向根节点
        if left:
            while left.right:
                left = left.right

            pRootOfTree.left, left.right = left, pRootOfTree

        # 递归处理右子树
        self.Convert(pRootOfTree.right)
        right = pRootOfTree.right

        # 将根节点右指针指向右子树最左孩子，右子树最左孩子的左指针指向根节点
        if right:
            while right.left:
                right = right.left

            pRootOfTree.right, right.left = right, pRootOfTree

        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left

        return pRootOfTree

发表于 2020-01-18 16:57:45 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class Solution:
    def Convernode(self,pRoot):
        if pRoot==None:
            return
        pcurrent=pRoot
        #左子树递归，求该子树对应链表的最后一个节点
        if pcurrent.left!=None:
            self.Convernode(pcurrent.left)
        #将左子树的最后一个节点与根节点确定前驱和后继关系
        pcurrent.left=self.plastnode
        if self.plastnode!=None:
            self.plastnode.right=pcurrent
        self.plastnode=pcurrent
        #右子树递归，求该子树对应的链表的最后一个节点
        if pcurrent.right!=None:
            self.Convernode(pcurrent.right)
    def Convert(self, pRoot):
        #使用plastnode作为全局变量，即总是指向双向链表的最后一个节点
        self.plastnode=None
        self.Convernode(pRoot)
        pheadoflist=self.plastnode
        #此时的pheadoflist指向的链表最后一个元素
        while(pheadoflist!=None and pheadoflist.left!=None):
            pheadoflist=pheadoflist.left
        #此时为链表头
        return pheadoflist
这个题主要考虑的是二叉搜索树转化为一个排序的双向链表，其中二叉搜索的一个节点有左孩子指针还有右孩子指针，与双向链表的节点的前驱节点和后继节点是相互对应。另外对于排序问题，我们可以使用中序遍历的方法，因为中序遍历后是以从小到大的顺序进行遍历二叉搜索的。所以只需要在中序遍历时给现在正在处理的节点以及前一个递归的最后一个节点进行前驱和后继处理就行
发表于 2019-12-22 10:07:26 回复(0)
Python
Kirto先森头像 Kirto先森 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        #中序遍历递归写法
        #只用一次，防止pRootOfTree为空
        if not pRootOfTree:
            return None
        #递归停止条件:遇到叶节点
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree
        #左子树最右节点和当前根节点相连
        left = self.Convert(pRootOfTree.left)
        p = left
        if left:
            while p.right:
                p = p.right
            p.right = pRootOfTree
            pRootOfTree.left = p
        #右子树最左节点和当前根节点相连
        #为什么不需要找到右子树最左节点? 因为中序遍历默认返回最左节点
        right = self.Convert(pRootOfTree.right)
        if right:
            right.left = pRootOfTree
            pRootOfTree.right = right
        #返回链表开头元素
        return left if left else pRootOfTree

        '''
        #中序遍历迭代写法 
        if not pRootOfTree:
            return None
        stack = []
        root = pRootOfTree
        pre = None
        while stack or pRootOfTree:
            if pRootOfTree:
                stack.append(pRootOfTree)
                pRootOfTree = pRootOfTree.left
            else:
                cur = stack.pop()
                if pre:
                    pre.right = cur
                    cur.left = pre
                pre = cur
                pRootOfTree = cur.right
        while root.left:
            root = root.left
        return root
        '''

发表于 2019-11-09 16:52:22 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
用中序遍历把二叉搜索树中的元素放入一个列表中
然后按顺序给列表中的元素绑定指针 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        def help(root):
            if not root:
                return []
            return help(root.left)+[root]+help(root.right)
        tlist=help(pRootOfTree)
        if not tlist:
            return
        for i in range(len(tlist)):
            if i+1<=len(tlist)-1:
                tlist[i].right=tlist[i+1]
            if i-1>=0:
                tlist[i].left=tlist[i-1]
        return tlist[0]


发表于 2019-11-01 13:48:46 回复(0)
Python
DevOps云原生头像 DevOps云原生 
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return
        s=[]
        res=[]
        p=None
        s.append(pRootOfTree)
        node=pRootOfTree.left
        while s or node:
            if node:
                s.append(node)
                node=node.left
            else:
                p=s.pop()
                res.append(p)
                node=p.right
        q=res[0]
        while res:
            top=res.pop(0)
            if res:
                top.right=res[0]
                res[0].left=top
        return q

首先，按照中序遍历二叉树的方式，得到一个有序的链表（按照通过即AC的要求，这里用list代替）
之后，对于这个已经有序的链表，开始循环的取节点，从头开始取，所以采用的不是一般的pop()，而是pop(0),
对于第i次这样取出的节点，是第i大的，而现在链表(用list代替)里的0索引位置的节点，是刚好在排序上比这个刚取出的节点大，那么，把刚取出的节点的right指针指向当前list索引为0的节点，并把list索引为0的节点的left指向刚取出的节点
编辑于 2019-10-15 01:27:37 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        p=pRootOfTree
        res=[]
        def midTraverse(root):
            if not root:
                return
            midTraverse(root.left)
            res.append(root)
            midTraverse(root.right)
        midTraverse(p)
        resP=res[0]
        while res:
            top=res.pop(0)
            if res:
                top.right=res[0]
                res[0].left=top
        return resP

发表于 2019-10-05 12:04:18 回复(0)
Python
G1011头像 G1011
Python
总结了一下个人认为 递归版和非递归版 最好的办法： 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#方法1：
# 递归
class Solution:
    def __init__(self):
        self.head = None
        self.rootHead = None
    def Convert(self, pRootOfTree):
        # write code here
        #主要思想：.
        #中序排列
        self.Convert_(pRootOfTree)
        return self.rootHead
    def Convert_(self,pRootOfTree):
        if pRootOfTree == None:
            return
        self.Convert_(pRootOfTree.left)
        if self.head is None:
            self.head = pRootOfTree
            self.rootHead = pRootOfTree
        else:
            self.head.right = pRootOfTree
            pRootOfTree.left = self.head
            self.head = pRootOfTree
        self.Convert_(pRootOfTree.right)
        
# 方法2：
# 非递归版本

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        stack =[]
        root = None
        pre = None
        p = pRootOfTree
        while p!= None or stack!=[]:
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            if not root:
                root = p
                pre = root
            else:
                pre.right = p
                p.left = pre
                pre = p
            p = p.right
        return root


发表于 2019-09-17 14:45:00 回复(0)
Python
璐上的枫烨头像 璐上的枫烨 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        if not (pRootOfTree.left or pRootOfTree.right):
            return pRootOfTree
        root = pRootOfTree
        while pRootOfTree:
            Head = pRootOfTree
            pRootOfTree = pRootOfTree.left
        if root.left:
            leftnode = self.ConvertLeft(root.left)
            root.left = leftnode
            leftnode.right = root
        if root.right:
            rightnode = self.ConvertRight(root.right)
            root.right = rightnode
            rightnode.left = root
        return Head
    def ConvertLeft(self, root):
        if not(root.right or root.left):
            return root
        connect = None
        if root.left:
            leftnode = self.ConvertLeft(root.left)
            root.left = leftnode
            leftnode.right = root
        if root.right:
            temp = root.right
            while temp:
                connect = temp
                temp = temp.right
            rightnode = self.ConvertRight(root.right)
            root.right = rightnode
            rightnode.left = root
        return root if not connect else connect

    def ConvertRight(self, root):
        if not(root.right or root.left):
            return root
        connect = None
        if root.left:
            temp = root.left
            while temp:
                connect = temp
                temp = temp.left
            leftnode = self.ConvertLeft(root.left)
            root.left = leftnode
            leftnode.right = root
        if root.right:
            rightnode = self.ConvertRight(root.right)
            root.right = rightnode
            rightnode.left = root
        return root if not connect else connect
这是个笨办法，大家见笑。
思路为：
1.对每个节点判断其是否有左右节点，如果有，则分别调用ConvertLeft()方法和ConvertRight()方法，这两个方法返回的是当前处理的节点的左子树转化的有序双向链表中的最后一个结点和右子树转化的有序双向链表中的第一个结点，然后将当前节点与返回的左右节点双向链接即可。
发表于 2019-09-10 14:04:09 回复(0)
Python
Jason_6868头像 Jason_6868 
class Solution:
    def __init__(self):
        """两个辅助指针，head用来返回表头，tail 用来变换指针"""
        self.Head = None
        self.Tail = None
        
    def Convert(self, pRootOfTree):
        """实际上就是中序遍历，只不过中间的打印节点变成了改变指针"""
        # write code here
        if not pRootOfTree:
            return
        self.Convert(pRootOfTree.left)
        '''这个if只执行一次，为了复制表头，和初始化需要改变的指针'''
        if not self.Head:
            self.Head = pRootOfTree
            self.Tail = pRootOfTree
        else:
            """当节点遍历到第二个（或者以后所有节点都一样）时，第一步把上一步这里节点一的right指向第二个节点，
            第二步把第二个点指回第一个点（这样就完成了双向指针）第三步把tail向后移动一步。"""
            self.Tail.right, pRootOfTree.left, self.Tail = pRootOfTree, self.Tail, pRootOfTree
        self.Convert(pRootOfTree.right)
        return self.Head
希望对大家有帮助， 实际核心代码就几行
发表于 2019-09-08 00:24:32 回复(0)
Python
加油sssssp在招手头像 加油sssssp在招手
python，逻辑很清楚简洁 
class Solution:
    def __init__(self):
        self.Head = None   #记录链表的头节点，用于最后算法的返回
        self.Tail = None   #链表尾节点，用于定位当前需要更改指向的节点
    def Convert(self, pRoot):
        if pRoot == None:
            return
        #中序遍历左子树部分的代码
        self.Convert(pRoot.left)
        #if语句只在中序遍历到第一个节点时调用，此后Head不变，Tail跟随算法进度而改变
        if self.Head == None:
            self.Head = pRoot
            self.Tail = pRoot
        #else三行语句是更改节点指向的代码
        else:
            self.Tail.right = pRoot
            pRoot.left = self.Tail
            self.Tail = pRoot     #尾结点后移一个节点
        #中序遍历右子树部分的代码
        self.Convert(pRoot.right)
        return self.Head


发表于 2019-08-26 22:55:34 回复(0)
提交观点

问题信息

分治
难度：
57条回答 153079浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号