前言
二叉樹作為一種重要的資料結構，在算法中起到了承前啟後的作用，它是數組和連結清單的延伸，也是圖的基礎。是以學習二叉樹的相關知識是十分有必要的，而在相關的操作中，二叉樹的周遊是最頻繁的，今天就來看看二叉樹的 4 種周遊方法！
二叉樹資料結構
所謂二叉樹，指的是每個結點最多有兩個分支的樹結構，其分支通常被稱為“左子樹”和“右子樹”，而且他們的次序是固定的，不能随意颠倒，一棵二叉樹的示例如下：
class TreeNode{
int val;
// 左子樹
TreeNode left;
// 右子樹
TreeNode right;
}
前序周遊
也叫做先序周遊，首先通路根節點，然後周遊左子樹，最後再周遊右子樹。而在周遊左右子樹時，仍然按照先通路根節點，然後周遊左子樹，最後周遊右子樹的方式，直到二叉樹為空則傳回！
周遊的方式又主要分為遞歸和疊代的方式，其具體實作如下所示。
遞歸
public ArrayList<Integer> preOrderReverse(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
preOrder(root, list);
return list;
public void preOrder(TreeNode root, ArrayList<Integer> list){
if(root != null){
list.add(root.val);
preOrder(root.left, list);
preOrder(root.right, list);
}
疊代
/**
* 用棧來進行疊代，由于棧是一種 先進後出 的資料結構，要輸出的順序是 中、左、右
* 是以我們優先将根節點加入 stack 後，然後先加入右子樹，再加入左子樹
*/
public ArrayList<Integer> preOrderReverse(TreeNode root){
// 棧，先進後出
Stack<TreeNode> stack = new Stack<>();
// 入棧
stack.push(root);
while(!stack.empty()){
// 出棧
TreeNode node = stack.pop();
list.add(node.val);
// 棧是一種先進後出的資料結構，是以先入右子樹，再入左子樹
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
中序周遊
首先周遊左子樹，然後通路根節點，最後再周遊右子樹。而在周遊左右子樹時，仍然按照先周遊左子樹，然後通路根節點，最後周遊右子樹的方式，直到二叉樹為空則傳回！
public ArrayList<Integer> inOrderReverse(TreeNode root){
inOrder(root, list);
public void inOrder(TreeNode root, ArrayList<Integer> list){
if(root != null){
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
* 中序周遊，按照 左、中、右 的順序列印
* 是以優先将左子樹壓入棧中，接着進行中間節點，最後處理右子樹
*
public ArrayList<Integer> inOrderReverse(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()){
// 節點不為空就一直壓棧
while(curr != null){
stack.push(curr);
// 考慮左子樹
curr = curr.left;
// 節點為空，出棧
curr = stack.pop();
// 加入目前值
list.add(curr.val);
// 考慮右子樹
curr = curr.right;
後序周遊
後序周遊首先周遊左子樹，然後周遊右子樹，最後通路根結點，在周遊左、右子樹時，仍然先周遊左子樹，然後周遊右子樹，最後周遊根結點，直到二叉樹為空則傳回！
public ArrayList<Integer> postOrderReverse(TreeNode root){
postOrder(root, list);
public void postOrder(TreeNode root, ArrayList<Integer> list){
postOrder(root.left, list);
postOrder(root.right, list);
List<Integer> list = new ArrayList<Integer>();
TreeNode current = root;
// 用來區分之前的結點是否被通路過
TreeNode last = null;
while(current != null || !stack.isEmpty()){
// 到樹的最左面
if(current != null){
stack.push(current);
current = current.left;
}else{
//看最左結點有沒有右子樹
current = stack.peek();
if(current.right != null && current.right != last){
current = current.right;
stack.push(current);
//右子樹再到最左
current = current.left;
}else{
//通路該結點，并标記被通路
current = stack.pop();
list.add(current.val);
last = current;
current = null;
層次周遊
層次周遊也叫做廣度優先周遊，它會優先通路離根節點最近的節點，其實作一般借助隊列實作。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<List<Integer>>();
if(root != null){
// 根節點不為 null，遞歸
dfs(1, root, lists);
return lists;
// index : 層數
public void dfs(int index, TreeNode root, List<List<Integer>> lists){
// 若 lists 中序列數小于層數，則将 lists 中加入一個空的序列
if(lists.size() < index){
lists.add(new ArrayList<Integer>());
// 然後将目前節點加入 lists 的子序列中
lists.get(index - 1).add(root.val);
// 以上就處理完 root 節點
// 接着處理左右子樹即可，處理時，層數到下一次，是以要 +1
if(root.left != null){
dfs(index + 1, root.left, lists);
if(root.right != null){
dfs(index + 1, root.right, lists);
ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) {
queue.add(root);
while (!queue.isEmpty()) {
// 擷取目前隊列的長度，這個長度相當于目前這一層的節點個數
int n = queue.size();
// 将隊列中的元素都拿出來(也就是擷取這一層的節點)，放到臨時list中
// 如果節點的左/右子樹不為空，也放入隊列中
List<Integer> level = new ArrayList<>();
int i = 0;
while(i < n){
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
if (node.right != null) {
queue.add(node.right);
i++;
// 将臨時list加入最終傳回結果中
res.add(level);
return res;
總結
以上就是資料結構二叉樹的 4 種周遊，如果你有更多關于各種周遊的實作，歡迎留言交流呀！
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)