引子：五分鐘玩轉(zhuǎn)面試考點-數(shù)據(jù)結(jié)構(gòu)系列梧田，不會像那種嚴肅淳蔼、古板的教科書般的博客文章，而是將晦澀難懂的概念和知識點盡可能幽默的細說出來裁眯，或結(jié)合生活場景鹉梨，或從零開始分析。帶給大家一個嚴肅而不失風趣的數(shù)據(jù)結(jié)構(gòu)穿稳。
說到二叉樹存皂，大家是不是第一個想起來的就是二叉樹的遍歷？
好吧逢艘，不管大家是不是旦袋，反正我是...
下面就直接進入正題吧：
首先樹的遍歷方法有：前序遍歷、中序遍歷它改、后序遍歷疤孕、層級遍歷。那這么多遍歷方法央拖，他們之間有什么聯(lián)系祭阀？
人之路徑，根之輸出和二叉樹遍歷有什么關聯(lián)鲜戒？
二叉樹的遍歷的口訣：
前序遍歷：根左右
中序遍歷：左根右
后序遍歷：左右根
于是柬讨，我按照這個口訣，使用遞歸法和迭代法對二叉樹進行了花式遍歷袍啡。于是就有了自己的一些看法：
- 無論是前、中却桶、后序遍歷境输，其實遍歷的路徑都是相同的。好像是一個人型颖系，（從根節(jié)點出發(fā)嗅剖，一直到二叉樹左下位置的節(jié)點的左孩子節(jié)點(null)此為一撇，然后再遍歷其右孩子節(jié)點(null)此為一捺）嘁扼。
- 遍歷的區(qū)別信粮，在于輸出根的時機不同，正如口訣所說：
前序遍歷："根左右"就是第一次執(zhí)行到根節(jié)點的時候（此時未遍歷孩子節(jié)點）趁啸，輸出根强缘；
中序遍歷："左根右"就是第二次執(zhí)行到根節(jié)點的時候（此時遍歷完左孩子節(jié)點）督惰，輸出根；
后序遍歷："根左右"就是第三次執(zhí)行到根節(jié)點的時候（此時遍歷完左右孩子節(jié)點）旅掂，輸出根赏胚；
由此我們可以看出，遍歷路徑是相同的商虐，輸出的都是根節(jié)點元素觉阅，只不過輸出時機不同！Ｃ爻怠典勇！
ps：什么？你不相信叮趴？那好割笙，咱們也寫一下代碼，看看是否符合口訣~
1. 遞歸法
1.1 前序遍歷
private static ArrayList<Integer> DLRTree(TreeNode root, ArrayList<Integer> list) {
//返回條件是null的情況下疫向，遞歸出口咳蔚，原樣返回list數(shù)組
if (root == null) {
return list;
}
//遞歸開始【根 左 右】
//遞歸邏輯
list.add(root.val); //list獲取數(shù)據(jù)
DLRTree(root.left, list); //遍歷左子樹
DLRTree(root.right, list); //遍歷右子樹
//遞歸返回式
return list;
}
心里默念：遞歸四要素
- 遞歸出口？
- 遞歸參數(shù)搔驼？
- 遞歸返回值谈火？
- 每次遞歸的處理邏輯？
- 遞歸出口：咱們是"人之路徑"舌涨。一撇在哪里終止糯耍？當左子樹為null的情況呀。一捺在哪里終止囊嘉？當發(fā)現(xiàn)右子樹節(jié)點為null的情況下呀温技。所以root==null為遞歸出口。
- 遞歸參數(shù)：父節(jié)點的左子樹節(jié)點或者右子樹節(jié)點扭粱。
- 遞歸返回值 ：ArrayList（引用傳遞）舵鳞，可以充當返回值。
- 遞歸處理邏輯：第一次訪問到根節(jié)點的時候輸出根琢蛤。
我想這個可以把他想成一個元素蜓堕，是不是好理解些：
1.2 中序遍歷
private static ArrayList<Integer> LDRTree(TreeNode root, ArrayList<Integer> list) {
//返回條件是null的情況下，遞歸出口博其，原樣返回list數(shù)組
if (root == null) {
return list;
}
//遞歸開始【左 根 右】
//遞歸邏輯
LDRTree(root.left, list); //遍歷左子樹
list.add(root.val);
LDRTree(root.right, list); //遍歷右子樹
//遞歸返回式
return list;
}
訪問完左子樹再次訪問根節(jié)點的時候套才，輸出根。
1.3 后序遍歷
private static ArrayList<Integer> LRDTree(TreeNode root, ArrayList<Integer> list) {
//返回條件是null的情況下慕淡，遞歸出口背伴，原樣返回list數(shù)組
if (root == null) {
return list;
}
//遞歸開始【左 根 右】
//遞歸邏輯
LRDTree(root.left, list); //遍歷左子樹
LRDTree(root.right, list); //遍歷右子樹
list.add(root.val); //在
//遞歸返回式
return list;
}
訪問完左右子樹再次訪問根節(jié)點的時候，輸出根。
2. 迭代法
PS：上面只是熱身運動傻寂，明白后息尺，咱們看看使用循環(huán)怎么遍歷二叉樹？我猜是使用棧崎逃！為啥掷倔？因為遞歸就是棧的思想...
當然，按照人之路徑个绍，將節(jié)點壓棧勒葱，此為一撇，直至節(jié)點是null巴柿，于是我們將節(jié)點出棧凛虽，找到"人"的連接點，完成一捺广恢。當然如果"捺"上面邏輯復雜凯旋，那么還是要走人之路徑的。什么時候結(jié)束操作钉迷？當最右節(jié)點完成出棧操作至非，棧中沒有數(shù)據(jù)。就是程序遍歷完畢糠聪。
上面說了根之輸出荒椭，那么第一次訪問根時，輸出根舰蟆，為前序遍歷趣惠。第二次訪問根時，輸出根身害，為中序遍歷味悄。第三次訪問根時，輸出根塌鸯，為后序遍歷侍瑟。
2.1 前序遍歷
//棧前序遍歷二叉樹(后進先出)
public static void stackDLRTree(TreeNode root) {
//借助棧，先序遍歷丙猬，根 左 右 根在第一次訪問時丢习，獲取數(shù)據(jù)
Stack<TreeNode> stack = new Stack<TreeNode>();
while (root != null || !stack.isEmpty()) {
//根打印的時機是 NO.1
while (root != null) {
//第一次訪問根節(jié)點，輸出并放入棧
System.out.println("前序遍歷 ： " + root.val);
stack.push(root); //將root節(jié)點放到棧中
root = root.left; //指針下移一位
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.right;
}
}
}
第一次將根壓棧的時候淮悼，輸出根。
2.2 中序遍歷
//中序遍歷（非遞歸）
public static void stackLDRTree(TreeNode root) {
//創(chuàng)建棧
Stack<TreeNode> stack = new Stack<TreeNode>();
//打印時機為左節(jié)點遍歷完畢之后
//棧 Root元素第一個進去揽思，若是出來的話杆故，
while (root != null || !stack.isEmpty()) {
while (root != null) {
//人——“撇”數(shù)據(jù)開始壓棧久锥，直到最 左下 節(jié)點（不為null）瓤逼。
stack.push(root);
root = root.left;
}
//人——“捺”回到再次根節(jié)點钧忽，準備訪問右節(jié)點。
//左節(jié)點訪問完畢塑径，此時，可以訪問右節(jié)點
root = stack.pop();
System.out.println("中序遍歷：" + root.val);
root = root.right; //準備完成 捺，也是按照撇的條件執(zhí)行
}
}
壓棧的時候是第一次操作根節(jié)點酒来，那么根節(jié)點彈出棧的時候，就是第二次操作根節(jié)點肪凛。此時輸出堰汉，便是中序遍歷。
2.3 后序遍歷
PS：壓棧第一次伟墙，彈棧第二次翘鸭。emmm，那后序遍歷怎么才是第三次呢戳葵？數(shù)據(jù)都不在棧里面了就乓！
是的，此時一個節(jié)點棧已經(jīng)不能滿足我們的需求了拱烁，無法三次操作棧中數(shù)據(jù)生蚁，于是我們可以在引入一個計數(shù)棧。同步統(tǒng)計根節(jié)點被訪問的次數(shù)戏自。計數(shù)棧數(shù)據(jù)需要和節(jié)點棧數(shù)據(jù)的位置保持一致邦投。
public static void stackLRDTree(TreeNode root) {
//節(jié)點棧
Stack<TreeNode> stackNode = new Stack<TreeNode>();
//計數(shù)棧
Stack<Integer> stackInt = new Stack<Integer>();
int count = 1; //標志位
//開始一撇
while (root != null || !stackNode.empty()) {
while (root != null) {
//1. root第一次被訪問，同步計數(shù)棧為0浦妄；
stackNode.push(root);
stackInt.push(0);
root = root.left;
}
//棧元素不為null尼摹，并且計數(shù)棧棧頂元素此時為1，此時是第三次被訪問到剂娄，
while (!stackNode.empty() && stackInt.peek() == count) {
//計數(shù)棧元素移除
stackInt.pop();
//獲取遍歷元素
System.out.println("后序遍歷" + stackNode.pop().val + " ");
}
//準備遍歷右節(jié)點
if (!stackNode.isEmpty()) {
//2. root被pop時蠢涝，是第二次被訪問到，同步計數(shù)棧為1
stackInt.pop();//移除元素0
stackInt.push(1);
//查看棧頂元素(但不移除)回到節(jié)點
root = stackNode.peek();
//準備一捺
root = root.right;
}
}
}
3. 層級遍歷
層級遍歷阅懦，其實使用的是隊列的數(shù)據(jù)結(jié)構(gòu)和二，將父元素輸出的時候，將子元素放入隊列中耳胎。后進后出惯吕。
//層級遍歷（使用隊列）
public static void levelTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode treeNode = null;
//創(chuàng)建隊列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root); //將根節(jié)點保存到隊列中
//輸出數(shù)據(jù)(隊列元素不空的情況下)
while (queue.size() != 0) {
treeNode = queue.poll(); //中間元素，保存信息
System.out.println("層級遍歷 ： " + treeNode.val + " ");
if (treeNode.left != null) {
//將指定的元素插入此隊列
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
}
上圖的描述是將每一層的元素均放到一個集合中怕午，那么如何確定元素位于某一層中废登？
使用層次遍歷時，借助queue隊列郁惜。每一層進入時堡距，隊列中的元素總量便是該層的節(jié)點數(shù)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> data = new ArrayList<>();
if(root==null){
return data;
}
java.util.Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
//獲取該層節(jié)點的數(shù)量
int count = queue.size();
List<Integer> list = new ArrayList<>();
//小循環(huán)，開始遍歷該層羽戒。
while (count > 0) {
//取出最左邊元素
TreeNode node = queue.poll();
//加到list中
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
count--;
}
data.add(list);
}
return data;
}
}
