二叉搜索樹(shù)與雙向鏈表
題目描述
輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表偏友。要求不能創(chuàng)建任何新的結(jié)點(diǎn)锹锰，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
思路
- 遞歸思想：把大問(wèn)題轉(zhuǎn)換為若干小問(wèn)題晴股；
- 由于JavaScript中并沒(méi)有鏈表或者Tree這樣的原生數(shù)據(jù)結(jié)構(gòu)，都是通過(guò)對(duì)象模擬的肺魁，因此最終要返回的是指向雙向鏈表首結(jié)點(diǎn)的指針电湘；
- 將左子樹(shù)構(gòu)成雙向鏈表，返回的是左子樹(shù)的尾結(jié)點(diǎn)鹅经，將其連接到root的左邊寂呛；
- 將右子樹(shù)構(gòu)成雙向鏈表，將其追加到root結(jié)點(diǎn)之后瘾晃，并返回尾結(jié)點(diǎn)贷痪；
- 向左遍歷返回的鏈表至頭結(jié)點(diǎn)處，即為所求雙向鏈表的首結(jié)點(diǎn)蹦误。
實(shí)現(xiàn)代碼
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree) {
if (!pRootOfTree) {
return null;
}
var lastNode = null;
lastNode = ConvertNode(pRootOfTree, lastNode);
var head = lastNode;
while (head && head.left) {
head = head.left;
}
return head;
}
function ConvertNode(node, lastNode) {
if (!node) {
return;
}
if (node.left) {
lastNode = ConvertNode(node.left, lastNode);
}
node.left = lastNode;
if (lastNode) {
lastNode.right = node;
}
lastNode = node;
if (node.right) {
lastNode = ConvertNode(node.right, lastNode);
}
return lastNode;
}
