牛客网-二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思路:

(1)二叉树的中序遍历,将中序遍历前一节点的右指针指向当前节点,当前节点的左指针指向前一节点。

(2)考虑数的中序遍历可以用栈或者递归。

1.栈

(1)把当前节点的左子树压栈,最后一个左叶节点设为双向链表的开始节点。

(2)弹出节点,并设前一节点右指针和当前节点左指针,当前弹出的节点有右子树的话,就继续将左子树都压栈。

2.递归

(1)先将左子树转为双向链表

(2)移动左子树构成链表的指针到达最后一个节点

(3)若左子树链表不为空,将根节点加在最后一个节点后

(4)将右子树转为双向链表

(5)右子树不为空加在根节点后

(6)根据左子树链表是否为空确定返回节点

代码:

1.栈实现中序遍历

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        stack = []
        p = pRootOfTree
        pre = None
        root =None
        while(p!=None or len(stack)!=0):
            while(p):
                stack.append(p)
                p = p.left
            p = stack.pop()
            if pre==None:
                root = p
                pre = p
            else:
                pre.right = p
                p.left = pre
                pre = p
            p = p.right
        return root

2.递归

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree==None:
            return None
        if pRootOfTree.right==None and pRootOfTree.left==None:
            return pRootOfTree
        left = self.Convert(pRootOfTree.left)
        p = left
        while(p!=None and p.right!=None):
            p=p.right
        if left!=None:
            p.right = pRootOfTree
            pRootOfTree.left = p
        right = self.Convert(pRootOfTree.right)
        if right != None:
            pRootOfTree.right = right
            right.left = pRootOfTree
        return left if left!=None else pRootOfTree

 题目链接:

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

根据最高票讨论写出来的

上一篇:剑指offer-面试题36-二叉搜索树与双向链表-中序遍历


下一篇:JS——树形导航菜单(html的ul嵌套,jQuery的css(),show(),hide(),index()等方法)