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 运行通过,请放心食用~




推荐阅读



学习交流 Go 语言,扫码回复「进群」即可


站长 polarisxu

自己的原创文章

不限于 Go 技术

职场和创业经验


Go语言中文网

每天为你

分享 Go 知识

Go爱好者值得关注


浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报