輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，要求不能創建任何新的結點，只能調整樹中結點指標的指向
解題思路
我們知道，二叉搜索樹的中序遍歷結果是有序的，因此我們第一個想到的就是使用中序遍歷，在這個程序中對結點進行操作
public class Solution {
// 標記上一次入堆疊值
private TreeNode preNode = null;
private TreeNode head = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
midShow(pRootOfTree);
return head;
}
public void midShow(TreeNode pRootOfTree) {
if(pRootOfTree.left != null) {
midShow(pRootOfTree.left);
}
if(preNode == null) {
head = pRootOfTree;
preNode = pRootOfTree;
} else {
preNode.right = pRootOfTree;
pRootOfTree.left = preNode;
preNode = pRootOfTree;
}
if(pRootOfTree.right != null) {
midShow(pRootOfTree.right);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/167660.html
標籤：其他
下一篇：Eclipse部署虛擬專案目錄