如何通过二叉树中序遍历生成双向链表?

1 个回答

  • 秦尘
    浪漫的灵魂从不向平淡的日子妥协。

    用中序遍历在原树上改指针生成双向链表:最左边的节点当头,左指针指向前驱,右指针指向后继,不新建节点。二叉搜索树中序遍历是升序的,按左、根、右处理,连出来就是排好序的双向链表。先从根一直往左走到没有左孩子,这个节点值最小,作为要返回的链表头。再递归做中序遍历,另外记一个前驱指针 pre,一开始为空。处理当前节点时,先递归左子树;回来后把当前节点的左指针指到 pre,pre 不为空时再把 pre 的右指针指到当前节点;然后把 pre 移到当前节点,最后递归右子树。这样每个节点都和前后邻居接上了,空间是 O(1),时间是 O(n),最后返回最左边那个头节点。

    func Convert(pRootOfTree *TreeNode) *TreeNode {
        if pRootOfTree == nil {
            return nil
        }
        p := pRootOfTree
        for p.Left != nil {
            p = p.Left
        }
        inOrder(pRootOfTree)
        return p
    }
    
    var pre *TreeNode
    
    func inOrder(root *TreeNode) {
        if root == nil {
            return
        }
        inOrder(root.Left)
        root.Left = pre
        if pre != nil {
            pre.Right = root
        }
        pre = root
        inOrder(root.Right)
    }
    
    参考来源:https://www.cnblogs.com/jiangzhou/p/18849473
    发布于 2026-11-17 14:04 •IP属地 河南
    举报
    评论
    收藏