Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/
2 5
/ \
3 4 6
The flattened tree should look like:
1
2
3
4
5
6
題意：用二叉樹的右節(jié)點(diǎn)當(dāng)做鏈表的next節(jié)點(diǎn)贤笆，把一個(gè)二叉樹轉(zhuǎn)換為鏈表的形式。
思路：
把二叉樹轉(zhuǎn)成一個(gè)鏈表的關(guān)鍵點(diǎn)是怎么把左子樹連接在根節(jié)點(diǎn)和右子樹中間禁添。
假設(shè)左右子樹已經(jīng)分別轉(zhuǎn)為鏈表了羹奉，那么如果知道了這個(gè)鏈表的頭部和尾部，用根節(jié)點(diǎn)連接左子樹鏈表的頭部洲胖，再用左子樹鏈表的尾部連接右子樹鏈表的頭部尖奔，就完成了二叉樹到鏈表的轉(zhuǎn)換征绎。
因此可以用分治的方法解決這道題，先求左右子樹轉(zhuǎn)換成的鏈表昔善，這個(gè)鏈表需要定義一個(gè)結(jié)構(gòu)來標(biāo)記頭和尾元潘，再把根節(jié)點(diǎn)和兩個(gè)鏈表連接起來，返回給上一層連接后的鏈表結(jié)構(gòu)君仆。
分治的時(shí)候要注意左右子樹為空的情況翩概，不同的情況，頭和尾指向哪里是不一樣的返咱。
class Result {
TreeNode head;
TreeNode tail;
}
public void flatten(TreeNode root) {
helper(root);
}
public Result helper(TreeNode root) {
if (root == null) {
return null;
}
//初始化當(dāng)前鏈表的頭尾
Result res = new Result();
res.head = root;
res.tail = root;
//求左右子樹轉(zhuǎn)換的鏈表
Result left = helper(root.left);
Result right = helper(root.right);
//不同情況下钥庇，連接根節(jié)點(diǎn)和左右鏈表，并更新當(dāng)前鏈表尾部
if (left != null && right != null) {
root.right = left.head;
root.left = null;
left.tail.right = right.head;
res.tail = right.tail;
} else if (root.left != null) {
root.right = left.head;
root.left = null;
res.tail = left.tail;
} else if (root.right != null) {
root.right = right.head;
res.tail = right.tail;
}
return res;
}