二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

NO IMAGE

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

LeetCode 傳送門(中序遍歷動畫是錯的):LeetCode 二叉樹專題講解

參考鏈接:

樹、二叉樹的前中後層序遍歷(遞歸、非遞歸Java實現)

樹的遍歷

二叉樹的前序,中序,後序遍歷方法總結

先根遍歷、中根遍歷和後根遍歷

核心思維模型:對於二叉樹的遍歷,首先要將 Base Case 具體化出來,最底層的子節點不是沒有左、右兩個子節點,應該將其左、右兩個子節點用 null 表示出來。即最底層子節點的左、右子節點都是 null。

在每次遞歸遍歷中,該子節點相對於本次遍歷都是一個根節點,它的左右子節點即使都是null,也是有左右子節點的!對於遞歸方法,最底層子節點和一個普通的根節點沒有任何區別。

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

先根遍歷遞歸 Pre-Order Traversal

深度優先遍歷 – 前序遍歷:
F, B, A, D, C, E, G, I, H.

public void preOrder(BinaryTreeNode root) {
//Base Case
if(root == null) return;
System.out.print(root.value);
//遍歷左子樹
preOrder(root.left);
//遍歷右子樹
preOrder(root.right);
}

先根遍歷迭代

深入優先遍歷二叉樹需要藉助棧結構來實現。

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

/**
* 先根遍歷迭代法
*/
public List<Integer> preOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<BinaryTreeNode> stack = new Stack<>();
//第一步:將根節點壓入棧中
stack.push(root);
BinaryTreeNode curNode;
while(!stack.isEmpty()) {
//第二步:將根節點彈出棧,並將值加入List集合,根節點遍歷完成
curNode = stack.pop();
list.add(curNode.value);
//第三步:根據深度優先搜索二叉樹的先根遍歷規則,需要先遍歷左子樹,然後才是右子樹
//結合棧的FILO 先入後出原則,先壓右子節點,再壓左子節點。
//當再次循環彈出頂部元素時,最先彈出的就是左子節點,此時由於是深入優先,所以右子
//節點繼續乖乖呆在棧底待命,直到左子樹所有節點都入棧並出棧之後,最後才彈出第一次
//壓入棧底的右子節點,最後才是對右子樹進行遍歷。
if(curNode.right != null) {
stack.push(curNode.right);
}
//第四步:壓入左子節點到棧頂,等待下一次循環時首先彈出得到遍歷
if(curNode.left != null) {
stack.push(curNode.left);
}
}
return list;
}

中根遍歷遞歸 In-Order Traversal

深度優先遍歷 – 中根遍歷:
A, B, C, D, E, F, G, H, I.

public void inOrder(BinaryTreeNode root) {
if(root == null) return;
inOder(root.left);
System.out.print(root.value);
inOder(root.right);
}

中根遍歷迭代法

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

public List<Integer> inOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<BinaryTreeNode> stack = new Stack<>();
BinaryTreeNode curNode = root;
while(!stack.isEmpty() || curNode != null) {
//這一部分實現了遞歸添加左節點的作用。
//首先遍歷左子節點,包括根節點都入棧,由於是中序遍歷,所以根節點在左子樹全部
//節點出棧完畢之後跟著出棧,然後根節點的右子樹再走一遍這個相同循環流程
while(curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
//這一部分實現了對根節點的遍歷,同時將指針指向了右子樹,在下輪中遍歷右子樹。
//每次出棧即遍歷完一個節點,需要把當前節點的指針移動到右子節點,不管當前節點
//的右子節點是否為null。如果是null,下次循環就直接走到出棧流程,把當前節點的
//根節點彈出(此處以左子節點為例:根節點早於左子節點入棧),此時該
//根節點剛好有右子節點,指針移動到右子節點,接著繼續執行相同的循環。直到當前
//節點和棧都為空,表明遍歷結束。
if(!stack.isEmpty()) {
curNode = stack.pop();
list.add(curNode.value);
curNode = curNode.right;
}
}
return list;
}

後根遍歷遞歸 Post-Order Traversal

深度優先搜索 – 後序遍歷:
A, C, E, D, B, H, I, G, F.

public void postOrder(BinaryTreeNode root) {
if(root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value);
}

後根遍歷迭代法(雙棧法)

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

    /**
* 參考:https://segmentfault.com/a/1190000016674584?utm_medium=referral&utm_source=tuicool
* 仔細觀察一下後序遍歷的順序:左 -- 右 -- 根
* 根節點在最後,對照先序遍歷的順序:根 -- 左 -- 右
* 這裡我們可以想到,將先序遍歷微調為:根 -- 右 -- 左的順序,這個微調很簡單,只是在push節點到棧
* 裡時,先push左節點,再push右節點,此時棧頂是右節點,那麼下次循環就會先彈出右節點,此時,
* 再把彈出的右節點push到反向棧 stackReverse 裡即可。
* 核心:我們只需要增加一個棧來反向輸出微調之後的先序遍歷的每個節點,就可以得到後序遍歷順序。
*/
public List<Integer> postOrderTraversal(BinaryTreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<BinaryTreeNode> stack = new Stack<>();
Stack<BinaryTreeNode> stackReverse = new Stack<>();
stack.push(root);
BinaryTreeNode curNode;
while (!stack.isEmpty()) {
curNode = stack.pop();
stackReverse.push(curNode);
if (curNode.left != null) {
stack.push(curNode.left);
}
if(curNode.right != null) {
stack.push(curNode.right);
}
}
while(!stackReverse.isEmpty()) {
curNode = stackReverse.pop();
list.add(curNode.value);
}
return list;
}

注意:由於雙棧法使用了額外的棧空間,也增加了一個循環,還可以優化。

後根遍歷迭代法(使用Deque,即雙向隊列法)

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

二叉樹遍歷Java(遞歸+迭代):前序、中序和後續遍歷(雙棧法+Deque法)

/**
* 雙向隊列法和先序遍歷迭代的區別只是使用了 Deque 這種鏈表數據結構,每次都
* 從鏈表頭插入新節點。由於 LinkedList 本身已經實現了 Deque 接口和List接口,因此
* LinkedList 可以作為一個雙向隊列來使用,同時本身也是List的實現類。可以很方便地
* 實現將新節點插入到表頭的需求。
*/
public List<Integer> postOrderTraversalByDeque(BinaryTreeNode root) {
LinkedList<Integer> resultList = new LinkedList<>();
if (root == null) return resultList;
Stack<BinaryTreeNode> stack = new Stack<>();
stack.push(root);
BinaryTreeNode curNode;
while(!stack.isEmpty()) {
curNode = stack.pop();
resultList.addFirst(curNode.value);
if (curNode.left != null) {
stack.push(curNode.left);
}
if (curNode.right != null) {
stack.push(curNode.right);
}
}
return resultList;
}

相關文章

再見2019展望未來|年度徵文

JS高級之手寫一個Promise,Generator,async和await【近1W字】

值得期待的JavaScript新特性

手把手教你做最好的電商搜索引擎(1)類目預測