如何通过二叉树中序遍历生成双向链表?
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属地 河南举报评论收藏
公众号进入网站体验更佳

