Go 刷 leetcode|二叉树展开为链表
Go语言精选
共 2208字,需浏览 5分钟
·
2020-08-12 02:07
今天为大家讲解 LeetCode 第 114 题,继续来一道关于?的题目
题目描述
给定一个二叉树,原地将它展开为一个单链表。
例如,给定二叉树
1
/ \
2 5
/ \ \
3 4 6将其展开为:
1
\
2
\
3
\
4
\
5
\
6来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
虽然题目没说如何展开,但是可以发现展开的顺序其实就是二叉树的先序遍历。
解法一
我们需要两步完成这道题。
将左子树插入到右子树的地方 将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null
过程如下展示
1
/ \
2 5
/ \ \
3 4 6
//将 1 的左子树插入到右子树的地方
1
\
2 5
/ \ \
3 4 6
//将原来的右子树接到左子树的最右边节点
1
\
2
/ \
3 4
\
5
\
6
//将 2 的左子树插入到右子树的地方
1
\
2
\
3 4
\
5
\
6
//将原来的右子树接到左子树的最右边节点
1
\
2
\
3
\
4
\
5
\
6
代码实现如下
//go
func flatten(root *TreeNode) {
for root != nil {
if root.Left == nil {
root = root.Right
}else {
pre := root.Left
for pre.Right != nil {
pre = pre.Right
}
pre.Right = root.Right
root.Right = root.Left
root.Left = nil
root = root.Right
}
}
}
//java
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null,直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点 pre
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;
// 考虑下一个节点
root = root.right;
}
}
}
方法二
先序遍历为1-2-3-4-5-6,如果按照先序遍历执行,1的左孩子为nil,右孩子为2,但是5就没了。所以不能直接使用先序遍历。
但是我们可以逆先序遍历:6-5-4-3-2-1
然后每遍历一个节点就将当前节点的右指针更新为上一个节点。
遍历到 5,把 5 的右指针指向 6。6 <- 5 4 3 2 1。
遍历到 4,把 4 的右指针指向 5。6 <- 5 <- 4 3 2 1。
……
(这个思想打个比方就像接链条,我们先把尾部的接好,在往头部拼接,整体就串起来了)
//go
func flatten(root *TreeNode) {
if root==nil{
return
}
var pre *TreeNode
//使用2重指针
dfs(root,pre)
}
func dfs(root *TreeNode,pre *TreeNode){
if root==nil{
return
}
dfs(root.Right,pre)
dfs(root.Left,pre)
root.Right= pre
root.Left=nil
pre =root
}
// go中用下面这种写法不知道为啥在LeetCode通过不了?♂️如有大佬知晓还请指点迷惑
// var pre *TreeNode = nil
// func flatten(root *TreeNode) {
// if root == nil {
// return
// }
// flatten(root.Right)
// flatten(root.Left)
// root.Right = pre
// root.Left = nil
// pre = root
// }
//java
private TreeNode pre = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
}
郑重声明:
所展示代码已通过 LeetCode 运行通过,请放心食用~
推荐阅读
站长 polarisxu
自己的原创文章
不限于 Go 技术
职场和创业经验
Go语言中文网
每天为你
分享 Go 知识
Go爱好者值得关注
评论