前言：
在之前，我們寫到了二叉樹的遞回 先、中、后序的遍歷方式，今天，來討論這三種遍歷方式的非遞回實作！！
先序遍歷
思路： 類似于層序遍歷
- 創建一個堆疊，先把根節點入堆疊
- 回圈取堆疊頂元素，并訪問(列印)
- 把當前節點的左 / 右子樹分別入堆疊
- 當堆疊為空時，遍歷結束
代碼實作：
public List<Integer> preorderTraversal(Node root) {
List<Integer> result = new ArrayList<>();
// 空樹判斷
if(root == null){
return result;
}
// 創建一個堆疊
Stack<Node> stack = new Stack<>();
Node cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){
result.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return result;
}
中序遍歷
思路：
仍然先要創建一個堆疊，創建一個 cur ，從根節點出發，回圈往左找，一直找到 null 為止，路徑上遇到的節點都入堆疊
遇到 null 的時候，就取堆疊頂元素，并訪問(列印)
再讓 cur 從當前堆疊頂元素的右子樹出發，回圈剛才的程序
代碼實作：
public List<Integer> inorderTraversal(Node root) {
//創建一個List
List<Integer> result = new ArrayList<>();
//空樹判斷
if(root == null){
return result;
}
Stack<Node> stack = new Stack<>();
Node cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
return result;
}
后序遍歷
思路： 和中序遍歷很像
先創建一個堆疊，創建一個 cur，從根節點出發，回圈往左找，一直找到 null 為止，路徑上遇到的節點都入堆疊，(此時還不能訪問，若堆疊頂元素的右子樹為 null，或右子樹已經被訪問過了，才能訪問堆疊頂元素)
右子樹是否已經訪問：使用一個 prev 記錄下后序遍歷程序中最后一個被訪問到的元素
代碼實作：
public List<Integer> postorderTraversal(Node root) {
//創建一個List
List<Integer> result = new ArrayList<>();
//空樹判斷
if(root == null){
return result;
}
Stack<Node> stack = new Stack<>();
Node cur = root;
Node prev = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(cur.right == null || cur.right == prev){
result.add(cur.val);
prev = cur;
cur = null;
}
else {
stack.push(cur);
cur = cur.right;
}
}
return result;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348374.html
標籤：其他
上一篇：【python資料結構】多維陣列