二叉樹（Binary tree）是樹形結構的一個重要類型。遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。二叉樹遍歷又分為二叉樹先序遍歷、二叉樹中序遍歷和二叉樹后續遍歷，之前我們已經介紹過了二叉樹的前序遍歷和中序遍歷，本文我們就講一講剩下的二叉樹后序遍歷。

二叉樹后續遍歷的口訣：左右根。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后遍歷根結點。即：

若二叉樹為空則結束返回，

否則：

（1）后序遍歷左子樹

（2）后序遍歷右子樹

（3）訪問根結點

二叉樹后續遍歷的實現分為遞歸和非遞歸兩者情況：

1.遞歸版的后序遍歷的代碼實現：

public static void posOrderRecur(Node head) {

????????if (head == null) {

????????????return;

????????}

????????posOrderRecur(head.left);

????????posOrderRecur(head.right);

????????System.out.print(head.value + " ");

????}

2.非遞歸版的后序遍歷的代碼實現：

public static void posOrderUnRecur(Node head) {

???if (head != null) {

?????Stack<Node> s1 = new Stack<Node>();

?????Stack<Node> s2 = new Stack<Node>();

?????s1.push(head);

?????while (!s1.isEmpty()) {

???????head = s1.pop();

???????s2.push(head);

???????if (head.left != null) {

?????????s1.push(head.left);

???????}

???????if (head.right != null) {

?????????s1.push(head.right);

?????????}

?????}

?????while (!s2.isEmpty()) {

???????System.out.print(s2.pop().value + " ");

?????}

???}

?}

下面我們通過一道例題來說明二叉樹的后序遍歷：

輸入: [1,null,2,3]  

   1

    \

     2

    /

   3

輸出: [3,2,1]

解題思路:

遞歸很簡單

class Solution:

????def postorderTraversal(self, root: TreeNode) -> List[int]:

????????res = []

????????def helper(root):

????????????if not root:

????????????????return

????????????helper(root.left)

????????????helper(root.right)

????????????res.append(root.val)

????????helper(root)

????????return res

java

class Solution {

????public List<Integer> postorderTraversal(TreeNode root) {

??????List<Integer> res = new ArrayList<>();

????????helper(root, res);

????????return res;

????}

????private void helper(TreeNode root, List<Integer> res) {

????????if (root == null) return;

????????helper(root.left, res);

????????helper(root.right, res);

????????res.add(root.val);

????}}

迭代,提供兩種方法

一種,反過來的前序遍歷;另一種, 記錄節點是否訪問過,訪問過便可彈出輸出!

方法一

class Solution:

????def postorderTraversal(self, root: TreeNode) -> List[int]:

????????res = []

????????p = root

????????stack = []

????????while p or stack:

????????????while p:

????????????????res.append(p.val)

????????????????stack.append(p)

????????????????p = p.right

????????????p = stack.pop().left

????????return res[::-1]

java

class Solution {

????public List<Integer> postorderTraversal(TreeNode root) {

????????Deque<TreeNode> stack = new LinkedList<>();

????????TreeNode p = root;

????????List<Integer> res = new ArrayList<>();

????????while (p != null || !stack.isEmpty()) {

????????????while (p != null) {

????????????????res.add(p.val);

????????????????stack.push(p);

????????????????p = p.right;

????????????}

????????????p = stack.pop().left;

????????}

????????Collections.reverse(res);

????????return res;

????}}

方法二

class Solution:

????def postorderTraversal(self, root: TreeNode) -> List[int]:

????????if not root: return []

????????stack = []

????????p = root

????????res = []

????????flag = []

????????while p or stack:

????????????while p:

????????????????flag.append(0)

????????????????stack.append(p)

????????????????p = p.left

????????????while stack and flag[-1] == 1:

????????????????flag.pop()

????????????????res.append(stack.pop().val)

????????????if stack:

????????????????flag[-1] = 1

????????????????p = stack[-1].right

????????return res

java

class Solution {

????public List<Integer> postorderTraversal(TreeNode root) {

????????Deque<TreeNode> stack = new LinkedList<>();

????????Deque<Integer> flag = new LinkedList<>();

????????TreeNode p = root;

????????List<Integer> res = new ArrayList<>();

????????while (p != null || !stack.isEmpty()) {

????????????while (p != null) {

????????????????flag.push(0);

????????????????stack.push(p);

????????????????p = p.left;

????????????}

????????????while (!stack.isEmpty() && flag.peek() == 1) {

????????????????flag.pop();

????????????????res.add(stack.pop().val);

????????????}

????????????if (!stack.isEmpty()) {

????????????????flag.pop();

????????????????flag.push(1);

????????????????p = stack.peek().right;

????????????}

????????}

????????return res;

????}}

看完了本文的二叉樹后序遍歷，我們再來回顧之前學的二叉樹先序遍歷和二叉樹中序遍歷，發現其實三者之間有很多的相似之處，區別就在于使每一個結點有且僅被訪問一次的規則和順序不同。我們只要能夠掌握其中的一種遍歷方式，實際上，其他的兩種遍歷方式也很容易推導出來了。在本站的數據結構和算法教程里面，還有許多優秀的數據結構和算法等待著我們去學習，勇攀知識的高峰。