实例解析二叉树后序遍历

二叉树（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;

    }}

看完了本文的二叉树后序遍历，我们再来回顾之前学的二叉树先序遍历和二叉树中序遍历，发现其实三者之间有很多的相似之处，区别就在于使每一个结点有且仅被访问一次的规则和顺序不同。我们只要能够掌握其中的一种遍历方式，实际上，其他的两种遍历方式也很容易推导出来了。在本站的数据结构和算法教程里面，还有许多优秀的数据结构和算法等待着我们去学习，勇攀知识的高峰。