題目描述
輸入一個(gè)二叉搜索樹甚颂，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表璧函。要求不能創(chuàng)建任何新的節(jié)點(diǎn)泣特，只能調(diào)整樹中節(jié)點(diǎn)指針的指向。
題目分析
- 題目要求是排好序的雙向鏈表散罕，二叉搜索樹的中序遍歷就是從小到大遍歷每個(gè)節(jié)點(diǎn)分歇，因此可以考慮和中序遍歷結(jié)合.
- 二叉樹由兩個(gè)指向子節(jié)點(diǎn)的指針，雙向鏈表也是類似的結(jié)構(gòu)欧漱，兩者結(jié)構(gòu)是類似的职抡，可以讓二叉樹的left指針作為鏈表指向前一個(gè)節(jié)點(diǎn)的指針，二叉樹right指針作為鏈表指向后一個(gè)節(jié)點(diǎn)的指針误甚。
- 對(duì)于二叉搜索樹的任何一個(gè)節(jié)點(diǎn)缚甩，它的前一個(gè)節(jié)點(diǎn)是其左子樹轉(zhuǎn)化成排序鏈表中的最后一個(gè)節(jié)點(diǎn)谱净，它的后一個(gè)節(jié)點(diǎn)是其由子樹轉(zhuǎn)化成鏈表后的第一個(gè)節(jié)點(diǎn)。很明顯可以通過(guò)遞歸來(lái)做擅威。
代碼
public TreeNode convert(TreeNode root){
if (root == null) {
return null;
}
// lastListNode是雙向鏈表的最后一個(gè)節(jié)點(diǎn)
TreeNode lastListNode = rConvert(root, null);
TreeNode headListNode = lastListNode;
// 找到雙向鏈表的頭節(jié)點(diǎn)并返回
while (headListNode != null && headListNode.left != null) {
headListNode = headListNode.left;
}
return headListNode;
}
/**
* @param curNode 二叉樹當(dāng)前節(jié)點(diǎn)
* @param lastListNode 當(dāng)前雙向鏈表的最后一個(gè)節(jié)點(diǎn)
* @return 雙向鏈表的最后一個(gè)節(jié)點(diǎn)
*/
TreeNode rConvert(TreeNode curNode, TreeNode lastListNode){
if (curNode == null) {
return null;
}
if (curNode.left != null) {
lastListNode = rConvert(curNode.left, lastListNode);
}
curNode.left = lastListNode;
if (lastListNode != null) {
lastListNode.right = curNode;
}
lastListNode = curNode;
if (curNode.right != null) {
lastListNode = rConvert(curNode.right, lastListNode);
}
return lastListNode;
}
