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

二叉樹后續(xù)遍歷的口訣：左右根。后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后遍歷根結(jié)點(diǎn)。即：

若二叉樹為空則結(jié)束返回，

否則：

（1）后序遍歷左子樹

（2）后序遍歷右子樹

（3）訪問根結(jié)點(diǎn)

二叉樹后續(xù)遍歷的實(shí)現(xiàn)分為遞歸和非遞歸兩者情況：

1.遞歸版的后序遍歷的代碼實(shí)現(xiàn)：

public static void posOrderRecur(Node head) {

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

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

????????}

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

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

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

????}

2.非遞歸版的后序遍歷的代碼實(shí)現(xiàn)：

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);

????}}

迭代,提供兩種方法

一種,反過來的前序遍歷;另一種, 記錄節(jié)點(diǎn)是否訪問過,訪問過便可彈出輸出!

方法一

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;

????}}

看完了本文的二叉樹后序遍歷，我們再來回顧之前學(xué)的二叉樹先序遍歷和二叉樹中序遍歷，發(fā)現(xiàn)其實(shí)三者之間有很多的相似之處，區(qū)別就在于使每一個結(jié)點(diǎn)有且僅被訪問一次的規(guī)則和順序不同。我們只要能夠掌握其中的一種遍歷方式，實(shí)際上，其他的兩種遍歷方式也很容易推導(dǎo)出來了。在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程里面，還有許多優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)和算法等待著我們?nèi)W(xué)習(xí)，勇攀知識的高峰。