主題
後序遍歷(Postorder Traversal)是二叉樹遍歷的一種方式。
其中節點的順序是先訪問左子樹,然後訪問右子樹,最後訪問根節點。
以下是後序遍歷的過程:
- 檢查當前節點是否為空。如果是空節點,則返回上一層。
- 從當前節點開始,先遞歸地後序遍歷左子樹。
- 接著,遞歸地後序遍歷右子樹。
- 最後,訪問當前節點。
這個遍歷過程可以使用遞歸或堆疊來實現。
以下是一個使用遞歸的後序遍歷的範例: 假設有以下二叉樹:
A
/ \
B C
/ \ \
D E F
後序遍歷的結果將是:D, E, B, F, C, A。
過程如下:
- 從根節點 A 開始:
- 遞歸地後序遍歷左子樹 B。
- 遞歸地後序遍歷左子樹 D。
- D 為葉子節點,訪問 D。
- 遞歸地後序遍歷右子樹 E。
- E 為葉子節點,訪問 E。
- 訪問 B。
- 遞歸地後序遍歷左子樹 D。
- 遞歸地後序遍歷右子樹 C。
- 遞歸地後序遍歷右子樹 F。
- F 為葉子節點,訪問 F。
- 訪問 C。
- 遞歸地後序遍歷右子樹 F。
- 訪問 A。
- 遞歸地後序遍歷左子樹 B。
因此,後序遍歷的結果為 D, E, B, F, C, A。
實作
// 定義二元樹節點的結構
class TreeNode {
constructor(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 後序遍歷函數
function postOrderTraversal(root) {
let result = [];
traversal(root, result);
return result;
}
// 後序遍歷函數,使用遞迴(recursion)來實作。
function traversal(root, result) {
if (root === null) {
return;
}
// 遍歷左子樹
traversal(root.left, result);
// 遍歷右子樹
traversal(root.right, result);
// 儲存根節點的值
result.push(root.val);
}
// 建立二元樹
/**
* 4
* / \
* 2 6
* / \ / \
* 1 3 5 7
* / \ / \/ \ / \
* n n n nn n n n
*/
const root = new TreeNode(
4,
new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
new TreeNode(6, new TreeNode(5, null, null), new TreeNode(7, null, null))
);
// 呼叫後序遍歷函數
const postOrderTraversalResult = postOrderTraversal(root);
console.log(postOrderTraversalResult); // 輸出:[1, 3, 2, 5, 7, 6, 4]
最後,如果你覺得我的分享對你有幫助,請給予我一個愛心,並且分享這篇文章,這將是對我最大的鼓勵!