題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表，要求不能創建任何新的結點，只能調整樹中結點指標的指向，
思路
二叉樹用遞回，代碼簡潔不易出錯，
準備
- 理解二叉搜索樹（不會的朋友自己百度）
- 不能創建任何新的結點，博主理解這句話的意思是題目不希望通過遍歷來的值保存在新創建的二叉樹中，而是希望通過我們操作指標來實作，
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode pre = null; //每次遞回之后用來保存雙向鏈表頭節點
TreeNode tail = null; //每次遞回之后用來保存雙向鏈表尾節點
public TreeNode Convert(TreeNode pRootOfTree) { //創建根節點為pRootOfTree的雙向鏈表，回傳頭節點
if (pRootOfTree == null) { //遞回的終止條件
return null;
}
Convert(pRootOfTree.left); //回傳左子樹的雙向鏈表
if (tail == null) {
pre = pRootOfTree;
tail = pRootOfTree;
}else {
tail.right = pRootOfTree;
pRootOfTree.left = tail;
tail = pRootOfTree;
}
Convert(pRootOfTree.right); //回傳右子樹的雙向鏈表
return pre;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/93087.html
標籤：其他