題目：輸入一棵二叉搜索樹碱茁，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)识颊，只能調(diào)整樹中結(jié)點(diǎn)指針的指向耿焊。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
代碼:
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
if(pRootOfTree.right == null && pRootOfTree.left == null){
return pRootOfTree;
}
TreeNode right = Convert(pRootOfTree.right);
if(right != null){
pRootOfTree.right = right;
right.left = pRootOfTree;
}
TreeNode left = Convert(pRootOfTree.left);
if(left == null){
return pRootOfTree;
}
TreeNode p = left;
while(p.right!= null){
p = p.right;
}
p.right = pRootOfTree;
pRootOfTree.left = p;
return left;
}
}
深度優(yōu)先遍歷揪惦，Convert返回的是子樹改為雙鏈表之后的尾節(jié)點(diǎn)，通過返回的左子樹構(gòu)成的鏈表獲得該鏈表的頭結(jié)點(diǎn)搀别，該層節(jié)點(diǎn)連接丹擎，右子樹的尾節(jié)點(diǎn)直接與本曾節(jié)點(diǎn)連接。之后再將連接之后的尾節(jié)點(diǎn)返回歇父。
- 如果該節(jié)點(diǎn)沒有左子樹蒂培，那么將右子樹轉(zhuǎn)換成鏈表，并與本節(jié)點(diǎn)連接之后榜苫，直接返回本節(jié)點(diǎn)即可护戳。
