十分钟搞懂LeetCode中二叉树前中后序遍历问题

什么是二叉树？

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树。二叉树的子树有左右之分，并且次序不能任意颠倒。二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决，当然也有一些可以使用非递归的思想解决。

需要注意二叉树本身就是递归定义的，所以大部分二叉树问题都能很好的用递归算法去解决。

二叉树的遍历

二叉树中最基础的问题就是二叉树的前序中序后序以及层次遍历，熟练掌握这几种方法对其他的二叉树问题有很大的帮助。

二叉树的遍历问题可以用递归和非递归（使用栈和队列）的方法来解决，一般来说递归算法的代码量较小更简单易懂。下面就让我们具体的一个个分析二叉树的遍历问题，在本文中我们只讨论递归算法，希望大家能深入了解递归的思想，其他栈，队列的解法大家可以自行研究一下。

二叉树的前序遍历

先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
递归方法具体思路：

首先判断终止条件：当当前节点为空则返回空

否则按左右的顺序依次打印

class Solution(object):
    def __init__(self):
        self.res = []
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        self.res.append(root.val)#每次遍历到根结点就把它加到队列中
        self.preorderTraversal(root.left)#当有左节点的时候就处理左节点
        self.preorderTraversal(root.right)#当同级没有左节点的时候再处理右节点
        return self.res

二叉树的中序遍历

中序遍历的顺序：左中右

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

递归的思路：在左子树存在时尽力遍历左子树，当到底的时候将左叶子节点添加进列表，将其父节点加入列表之后看父节点是否有右子树当只有右子树没有左子树时将右子树的值加入

左子树 ---> 根结点 ---> 右子树

class Solution(object):
    def __init__(self):
        self.res = []#必须要在这里声明一个属性不然每次调用就被置零了
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root != None:
            self.inorderTraversal(root.left)#先走到最左的叶子节点
            self.res.append(root.val)#当左节点全遍历完了添加父结点
            self.inorderTraversal(root.right)#之后看右子树
        return self.res

二叉树的后序遍历

后序遍历的顺序：左右中

class Solution(object):
    def __init__(self):
        self.ret = []#必须要在这里声明一个属性不然每次调用就被置零了
    def postorderTraversal(self, root):
        if root == None:
            return []
        self.postorderTraversal(root.left)        
        self.postorderTraversal(root.right)
        self.ret.append(root.val)
        return self.ret

小结

二叉树的前中后序遍历的算法本质上没有区别，只是顺序的差别（特别的是父节点用append（root.val）其他直接递归）

本质上是优先递归一种进到最底层然后一层层弹出。