二叉樹的遍歷 ★★★★★TreeNode 節點/ Definition for a binary tree node. /public class TreeNode {int val;TreeNode left;TreeNode right;

TreeNode(int x) {val = x;}}

遞歸調用 (深度優先遍歷) ★☆☆☆☆

public void preorderTraversal(TreeNode root) {

if (root == null) {

return;

}

// 可調整前、中、后序遍歷

System.out.print(root.val);

preorderTraversal(root.left);

preorderTraversal(root.right);

}

2.1 非遞歸遍歷 - 基于棧 (前序遍歷、深度優先遍歷) ★★★☆☆(不推薦)

public List preorderTraversalWithStack(TreeNode root) {

LinkedList output = new LinkedList<>(); // 用于回溯的棧 Stack stack = new Stack<>(); while (root != null || !stack.isEmpty()) { // 訪問結點的數據，并且移動到左子結點，直到無左子結點 while (root != null) { output.add(root.val); stack.push(root); // 將當前節點 push 到棧中，方便后續回溯 root = root.left; // 遍歷左子結點 } // 回溯，遍歷右子結點 if (!stack.isEmpty()) { root = stack.pop().right; } } return output;}2.2非遞歸遍歷 - 基于棧改進版(基于隊列的棧模式)(執行時間較上者提升1倍) ★★★★☆public List preorderTraversalWithStack(TreeNode root) { LinkedList output = new LinkedList<>(); // 用于回溯的棧(基于鏈表實現，不用擔心棧的擴容問題) LinkedList stack = new LinkedList<>(); while (root != null || !stack.isEmpty()) { // 訪問結點的數據，并且移動到左子結點，直到無左子結點 while (root != null) { output.add(root.val); stack.add(root); // 將當前節點 add 到棧中，方便后續回溯 root = root.left; // 遍歷左子結點 } // 回溯，遍歷右子結點 if (!stack.isEmpty()) { root = stack.pollLast().right; } } return output;}3. 非遞歸遍歷 - 基于隊列 (層次遍歷、廣度優先遍歷、O(n)) ★★★★☆public List levelorderTraversal(TreeNode root) { LinkedList output = new LinkedList<>(); if (root == null) { return output; } Queue queue = new LinkedList<>(); queue.add(root); // 遍歷隊列 while (!queue.isEmpty()) { // 從隊列頭部取出一個結點 root = queue.poll(); output.add(root.val); // 將左右子結點放入隊列尾部 if (root.left != null) { queue.add(root.left); } if (root.right != null) { queue.add(root.right); } } return output;}4. Morris Traversal(莫里斯遍歷、O(n)) ★★★★☆public List morrisTraversal(TreeNode root) { LinkedList output = new LinkedList<>(); TreeNode prev; TreeNode curr = root; while (curr != null) { // 向左子節點遍歷 if (curr.left != null) { prev = curr.left; while (prev.right != null && prev.right != curr) { prev = prev.right; } // 右子節點的回溯指針綁定 if (prev.right == null) { prev.right = curr; curr = curr.left; } else { output.add(curr.val); prev.right = null; curr = curr.right; } // 向右子節點遍歷 } else { output.add(curr.val); curr = curr.right; } } return output;}QQ討論群組：984370849 706564342 歡迎加入討論

QQ討論群組：984370849 706564342 歡迎加入討論

想要深入學習的同學們可以加入QQ群討論，有全套資源分享，經驗探討，沒錯，我們等著你，分享互相的故事!

總結

以上是生活随笔為你收集整理的前序遍历二叉树代码_二叉树遍历、二叉树深度、代码示例，一点课堂（多岸学院）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。