一冗懦、題目
給定一個二叉樹，原地將它展開為一個單鏈表隙赁。
例如垦藏，給定二叉樹
1
/ \
2 5
/ \ \
3 4 6
將其展開為：
1
\
2
\
3
\
4
\
5
\
6
二、遞歸解法
1. 解題思路
題目其實就是將二叉樹通過右指針伞访，組成一個單鏈表掂骏。
1 -> 2 -> 3 -> 4 -> 5 -> 6
思路1:
看到最后的單鏈表，很容易想到這是二叉樹先序遍歷的結(jié)果厚掷，我們先試試通過先序遍歷的思路去模擬弟灼。
先序遍歷的訪問順序就是1 2 3 4 5 6，
遍歷到1蝗肪，把1的右指針指向2袜爪，這時候會導(dǎo)致右孩子5找不到了蠕趁，通過全局變量記錄右孩子薛闪，發(fā)現(xiàn)當遍歷到2的時候，還是會存在同樣的問題俺陋，所以此方法行不通豁延。
那能不能遍歷1時先不動昙篙，遍歷到 2，把 1 的右指針指向 2呢诱咏，好像行得通苔可，我們先試試。1 -> 2 3 4 5 6袋狞。
遍歷到 3焚辅，把 2 的右指針指向 3。1 -> 2 -> 3 4 5 6苟鸯。
當遍歷原有4的節(jié)點時同蜻，發(fā)現(xiàn)此時找不到4了，已經(jīng)變成3了早处，同樣的湾蔓，5節(jié)點也找不到，此方法行不通砌梆，會出現(xiàn)右孩子找不到的情況默责。
這種右孩子丟失的問題解決呢？通過全局變量記錄的方法行不通咸包，那我們可不可以逆向思考一下桃序，我們先遍歷訪問右孩子節(jié)點呢？這就產(chǎn)生了思路2.
思路2：
我們依次遍歷 6 5 4 3 2 1诉儒，然后每遍歷一個節(jié)點就將當前節(jié)點的右指針更新為上一個訪問的節(jié)點葡缰。
首先訪問到6，記錄pre值
遍歷到 5忱反，把 5 的右指針指向 6泛释。6 <- 5 4 3 2 1。
遍歷到 4温算，把 4 的右指針指向 5怜校。6 <- 5 <- 4 3 2 1。
......
這樣就不會有丟失孩子的問題了注竿，因為更新當前的右指針的時候茄茁，當前節(jié)點的右孩子已經(jīng)訪問過了。
2. 編碼
由思路2可知巩割，對節(jié)點的訪問順序是6 5 4 3 2 1裙顽，實際上就是右子樹->左子樹->根節(jié)點，發(fā)現(xiàn)和二叉樹的后序遍歷很像宣谈，二叉樹的后序遍歷順序是右子樹->左子樹->根節(jié)點愈犹，我們只需稍微變通即可。
二叉樹后序遍歷遞歸代碼模版：
/**
* 后序遍歷遞歸 左子 右子 根
*/
fun postOrderTraverse(root: BTreeNode?) {
if (root == null) {
return
}
postOrderTraverse(root.left)
postOrderTraverse(root.right)
print("${root.value} ")
}
調(diào)換左右子樹的先后順序，即可得到此題的遞歸解法漩怎。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode pre = null;
public void flatten(TreeNode root) {
if(root == null ){
return ;
}
//左右子樹訪問順序相對于后序遍歷發(fā)生改變
flatten(root.right);
flatten(root.left);
//本題對遍歷了的節(jié)點處理
root.right = pre;
root.left = null;
pre = root;
}
}
3. 時空復(fù)雜度分析
時間復(fù)雜度：每個元素都必須訪問一次勋颖，所以是 O(n)
空間復(fù)雜度：最壞的情況下，需要存放 O(h) 個函數(shù)調(diào)用(h是樹的高度)勋锤，所以是 O(h)饭玲，h= logN
三、迭代解法
1. 解題思路
還是回歸到輸出結(jié)果叁执，發(fā)現(xiàn)就是先序遍歷的順序茄厘，所以可以做如下處理：
- 將左子樹插入到右子樹的地方
- 將原來的右子樹接到左子樹的最右邊節(jié)點
- 考慮新的右子樹的根節(jié)點，一直重復(fù)上邊的過程谈宛，直到新的右子樹為 null
圖解：
1 1
/ \
2 5 ---> 2 5
/ \ \ / \ \
3 4 6 3 4 6
//將 1 的左子樹插入到右子樹的地方
1
\
2 5
/ \ \
3 4 6
//將原來的右子樹接到左子樹的最右邊節(jié)點
1
\
2
/ \
3 4
\
5
\
6
//將 2 的左子樹插入到右子樹的地方
1
\
2
\
3 4
\
5
\
6
//將原來的右子樹接到左子樹的最右邊節(jié)點
1
\
2
\
3
\
4
\
5
\
6
......
2. 編碼
此題示例代碼：
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun flatten(node: TreeNode?): Unit {
var root = node
while(root!=null){
if(root.left == null ){
root = root?.right
}else{
//找到root左子樹的最右側(cè)節(jié)點
var leftTreeBottomNode = root?.left
while(leftTreeBottomNode.right!=null){
leftTreeBottomNode = leftTreeBottomNode.right
}
//將root右子樹拼接在leftTreeBottomNode的right指針
leftTreeBottomNode?.right = root?.right
root?.right = root?.left
root?.left = null
//處理下一個節(jié)點
root = root.right
}
}
}
}
3.時空復(fù)雜度分析
時間復(fù)雜度：每個元素都必須訪問一次蚕断，尋找左子樹的最右節(jié)點最差是O(h)，h = logN入挣， 所以是時間復(fù)雜度是O(NlogN)
空間復(fù)雜度：沒什么說的亿乳，O(1)
四、總結(jié)
- 此題難度為中等
- 對于二叉樹的二叉樹的遍歷径筏，有根 左子 右子（前序遍歷）葛假、左子 根 右子(中序遍歷)、左子 右子 根（后序遍歷）滋恬、 根 右子 左子聊训、右子 根 右子、 右子 右子 根恢氯。
leetcode傳送門：114. 二叉樹展開為鏈表
