JZ36 二叉搜索樹與雙向鏈表
描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表
注意:
1.要求不能創建任何新的結點，只能調整樹中結點指標的指向，當轉化完成以后，樹中節點的左指標需要指向前驅，樹中節點的右指標需要指向后繼
2.回傳鏈表中的第一個節點的指標
3.函式回傳的TreeNode，有左右指標，其實可以看成一個雙向鏈表的資料結構
4.你不用輸出雙向鏈表，程式會根據你的回傳值自動列印輸出
思路：
二叉樹中序遍歷除了遞回方法，我們還可以嘗試非遞回解法，與常規的非遞回中序遍歷幾乎相同，還是借助堆疊來輔助，只是增加了連接節點，
具體做法：
step 1：創建兩個指標，一個指向題目中要求的鏈表頭（head），一個指向當前遍歷的前一節點（pre)，創建一個布爾型變數，標記是否是第一次到最左，因為第一次到最左就是鏈表頭，
step 2：判斷空樹不能連接，
step 3：初始化一個堆疊輔助中序遍歷，
step 4：依次將父節點加入堆疊中，直接進入二叉樹最左端，
step 5：第一次進入最左，初始化head與pre，然后進入它的根節點開始連接，
step 6：最后將右子樹加入堆疊中，堆疊中依次就彈出“左中右”的節點順序，直到堆疊為空，
代碼
package mid.JZ36二叉搜索樹與雙向鏈表;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//頭節點
private TreeNode head = null;
//上一個節點
private TreeNode pre = null;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) return null;
//首先遞回到最左最小值
Convert(pRootOfTree.left);
if (pre == null) {
head = pRootOfTree;
pre = pRootOfTree;
} else {
pRootOfTree.left = pre;
pre.right = pRootOfTree;
pre = pRootOfTree;
}
//右遞回
Convert(pRootOfTree.right);
return head;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539497.html
標籤：其他
上一篇：<五>function的實作原理