目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
114.二叉树展开为链表
访问量:1091
一、简介
给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]
二、实现
思路:利用递归+二叉树前序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func flatten(root *TreeNode) { // top - left - right if root == nil || (root.Left == nil && root.Right == nil) { return } if root.Left == nil { flatten(root.Right) return } else if root.Right == nil { flatten(root.Left) root.Right = root.Left root.Left = nil } else { rightRoot := root.Right flatten(root.Left) root.Right = root.Left root.Left = nil p := root.Right for p.Right != nil { p = p.Right } flatten(rightRoot) // 排序右子树 p.Right = rightRoot } }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助