Go 刷 leetcode｜二叉樹展開為鏈表

今天為大家講解 LeetCode 第 114 題，繼續(xù)來一道關(guān)于?的題目

題目描述

給定一個(gè)二叉樹，原地將它展開為一個(gè)單鏈表。

例如，給定二叉樹

    1
   / \
  2   5
 / \   \
3   4   6

將其展開為：

1
?\
??2
???\
????3
?????\
??????4
???????\
????????5
?????????\
??????????6

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路

雖然題目沒說如何展開，但是可以發(fā)現(xiàn)展開的順序其實(shí)就是二叉樹的先序遍歷。

解法一

我們需要兩步完成這道題。

• 將左子樹插入到右子樹的地方
• 將原來的右子樹接到左子樹的最右邊節(jié)點(diǎn)

考慮新的右子樹的根節(jié)點(diǎn)，一直重復(fù)上邊的過程，直到新的右子樹為 null

過程如下展示

????1
???/?\
??2???5
?/?\???\
3???4???6

//將?1?的左子樹插入到右子樹的地方
????1
?????\
??????2?????????5
?????/?\?????????\
????3???4?????????6????????
//將原來的右子樹接到左子樹的最右邊節(jié)點(diǎn)
????1
?????\
??????2??????????
?????/?\??????????
????3???4??
?????????\
??????????5
???????????\
????????????6
????????????
?//將?2?的左子樹插入到右子樹的地方
????1
?????\
??????2??????????
???????\??????????
????????3???????4??
?????????????????\
??????????????????5
???????????????????\
????????????????????6???
????????
?//將原來的右子樹接到左子樹的最右邊節(jié)點(diǎn)
????1
?????\
??????2??????????
???????\??????????
????????3??????
?????????\
??????????4??
???????????\
????????????5
?????????????\
??????????????6?????????

代碼實(shí)現(xiàn)如下

//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，直接考慮下一個(gè)節(jié)點(diǎn)
????????if?(root.left?==?null)?{
????????????root?=?root.right;
????????}?else?{
????????????//?找左子樹最右邊的節(jié)點(diǎn)?pre
????????????TreeNode?pre?=?root.left;
????????????while?(pre.right?!=?null)?{
????????????????pre?=?pre.right;
????????????}?
????????????//將原來的右子樹接到左子樹的最右邊節(jié)點(diǎn)
????????????pre.right?=?root.right;
????????????//?將左子樹插入到右子樹的地方
????????????root.right?=?root.left;
????????????root.left?=?null;
????????????//?考慮下一個(gè)節(jié)點(diǎn)
????????????root?=?root.right;
????????}
????}
}

方法二

先序遍歷為1-2-3-4-5-6，如果按照先序遍歷執(zhí)行，1的左孩子為nil，右孩子為2，但是5就沒了。所以不能直接使用先序遍歷。

但是我們可以逆先序遍歷：6-5-4-3-2-1

然后每遍歷一個(gè)節(jié)點(diǎn)就將當(dāng)前節(jié)點(diǎn)的右指針更新為上一個(gè)節(jié)點(diǎn)。

遍歷到 5，把 5 的右指針指向 6。6 <- 5 4 3 2 1。

遍歷到 4，把 4 的右指針指向 5。6 <- 5 <- 4 3 2 1。

……

（這個(gè)思想打個(gè)比方就像接鏈條，我們先把尾部的接好，在往頭部拼接，整體就串起來了）

//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通過不了??♂?如有大佬知曉還請(qǐng)指點(diǎn)迷惑
//?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 運(yùn)行通過，請(qǐng)放心食用～