題目描述
給定一個二叉樹，原地將它展開為鏈表剃盾。
示例：
例如腺占，給定二叉樹
1
/ \
2 5
/ \ \
3 4 6
將其展開為：
1
\
2
\
3
\
4
\
5
\
6
思路
1.從根節(jié)點(diǎn)開始遍歷淤袜，依次遍歷右子樹，若當(dāng)前結(jié)點(diǎn)存在左子樹衰伯，則進(jìn)行如下操作铡羡。
- 遍歷當(dāng)前結(jié)點(diǎn)左子樹的右子樹，然后將左子樹與右子樹進(jìn)行拼接
- 將當(dāng)前結(jié)點(diǎn)的右子樹指針指向左子樹
- 將當(dāng)前結(jié)點(diǎn)的左子樹的指針置空
2.一直循環(huán)遍歷到右子樹結(jié)尾即可意鲸。
具體轉(zhuǎn)變過程烦周，可以參考下圖：
左子樹與右子樹相連
將當(dāng)前結(jié)點(diǎn)的右子樹指針指向左子樹
將當(dāng)前結(jié)點(diǎn)的左子樹的指針置空
Java代碼實(shí)現(xiàn)
public void flatten(TreeNode root) {
while(root != null){
//如果當(dāng)前結(jié)點(diǎn)的左子樹不為null，說明需要接到右子樹上
if(root.left != null){
TreeNode curLeft = root.left;
while(curLeft.right != null){
curLeft = curLeft.right;
}
//將左子樹與右子樹相連
curLeft.right = root.right;
//將當(dāng)前結(jié)點(diǎn)的右子樹指向改變
root.right = root.left;
//將當(dāng)前結(jié)點(diǎn)的左子樹置空
root.left = null;
}
//進(jìn)行下一個結(jié)點(diǎn)的轉(zhuǎn)換
root = root.right;
}
}
