Go 刷 leetcode｜二叉树展开为链表

今天为大家讲解 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 运行通过，请放心食用～