之前我們介紹了二叉樹前序排序的兩種方法绽榛，一種是遞歸北发，一種是迭代井赌。這兩種沒有什么大的差別闸翅。今天我們帶來了一種Morris遍歷
Morris 遍歷的核心思想是利用樹的大量空閑指針，實(shí)現(xiàn)空間開銷的極限縮減
其前序遍歷規(guī)則總結(jié)如下：
1辜伟， 新建臨時(shí)樹氓侧，令該節(jié)點(diǎn)為樹的根；
2导狡，如果當(dāng)前根的左子樹為空约巷，將當(dāng)前根放入數(shù)組，并將當(dāng)前根的右子樹更新為樹的根烘豌；
3载庭， 如果當(dāng)前根的左子樹不為空看彼，獲取到當(dāng)前根的左子樹：
3.1廊佩， 循環(huán)遍歷當(dāng)前根的左子樹的所有右子樹，獲取到最后一個(gè)不等于根的右子樹
3.1靖榕， 如果獲取到的右子樹為空标锄，將根節(jié)點(diǎn)放入數(shù)組，然后將根賦值給遍歷獲取到的右子樹的右子樹茁计。
3.2料皇， 如果獲取到的右子樹不為空，將獲取到的右子樹的右子樹刪除星压，同時(shí)將根的右子樹更新為樹的根
重復(fù)步驟 2 和步驟 3践剂，直到遍歷結(jié)束。
看到這里如果有一點(diǎn)點(diǎn)懵的話就看一下下面的圖娜膘，我會(huì)一步一步的將實(shí)現(xiàn)過程給畫出來逊脯。
第一步，我們獲取到樹的根F竣贪，然后獲取F的左子樹军洼，如果左子樹為空巩螃，我們就將F放入數(shù)組，然后獲取樹的右子樹更新為樹的根匕争。
這里左子樹不為空避乏，我們第一步拿到樹的左子樹B，然后遍歷B的所有右子樹甘桑，一直遍歷到右子樹為空并且右子樹不等于當(dāng)前根的情況拍皮，這里我們B本來就沒有右子樹，所以直接拿到B跑杭。
當(dāng)B的右子樹為空春缕，我們將F放入數(shù)組。然后將F放入B的右子樹艘蹋。
根節(jié)點(diǎn)指向B
第二步锄贼，我們獲取到樹的根 B，判斷B的左子樹女阀，如果左子樹為空宅荤，我們將就將B 放入數(shù)組，同時(shí)將根指向 F
第三步浸策，我們獲取到樹的根F冯键，判斷F的左子樹是否為空，這里樹的左子樹不為空庸汗，所以拿到樹的左子樹B 惫确，然后遍歷B的所有右子樹，一直遍歷到右子樹為空并且右子樹不等于根的情況蚯舱。
這里B的右子樹是等于根的改化，所以走恢復(fù)二叉樹的邏輯，將B的右子樹 清空枉昏，同時(shí)將根指向根的右子樹 A
第四步陈肛，我們獲取到樹的根A，判斷A的左子樹是否為空兄裂，這里樹的左子樹不為空句旱，所以拿到樹的左子樹D，然后遍歷D的所有右子樹晰奖，一直遍歷到右子樹為空并且右子樹不等于當(dāng)前根的情況谈撒，這里我們的D本來就沒有右子樹，所以直接拿到D 匾南，因?yàn)镈的右子樹為空啃匿，那么我們將根A放入到數(shù)組,將根A放入到D的右子樹。根節(jié)點(diǎn)指向D
第五步午衰，我們獲取到樹的根D立宜，判斷D的左子樹冒萄，如果D的左子樹為空，那么將D放入數(shù)組橙数，同時(shí)將根指向A
第六步尊流，我們獲取到樹的根A，判斷A的左子樹是否為空灯帮，這里A的左子樹是不為空的崖技，所以拿到A的左子樹D，然后遍歷D的所有右子樹钟哥，一直到右子樹為空并且右子樹不等于根迎献，這里D的右子樹等于根，我們走恢復(fù)二叉樹邏輯腻贰，將D的右子樹A刪除吁恍，然后將根指向A的右子樹C
第七步，我們獲取到樹的根C播演，判斷C的左子樹是否為空冀瓦，這里C的左子樹為空，那么將C放入數(shù)組写烤，同時(shí)將根指向C的右子樹翼闽，C的右子樹為空遍歷結(jié)束
經(jīng)過我們一步一步的拆解，是不是已經(jīng)感覺這個(gè)排序也超級(jí)簡單呢洲炊，現(xiàn)在上代碼
public static void main(String[] args) {
Solution solution = new Solution();
TreeNode t = new TreeNode("F", new TreeNode("B",null,null), new TreeNode("A", new TreeNode("D",null,null), new TreeNode("C",null,null)));
System.out.println(Morris_PreOrder(t));
}
public static List<String> Morris_PreOrder(TreeNode root) {
List res = new ArrayList<>();
if(root == null){
return res;
}
TreeNode cur = root;
while(cur != null) {
if(cur.left == null) {
res.add(cur.val);
cur = cur.right;
} else {
TreeNode tmp = cur.left;
while(tmp.right != null && tmp.right != cur){
tmp = tmp.right;
}
if(tmp.right == null) {
res.add(cur.val); //輸出當(dāng)前節(jié)點(diǎn)
tmp.right = cur; //將當(dāng)前根節(jié)點(diǎn)賦值給 最右子樹的右子樹
cur = cur.left;
} else {
tmp.right = null; //恢復(fù)二叉樹
cur = cur.right;
}
}
}
return res;
}
是春風(fēng)感局， 是余暉， 是一道曙光暂衡， 是未來可期询微。
手敲不易，點(diǎn)個(gè)贊唄
