python实现二叉树递归遍历与非递归遍历

一、中序遍历

前中后序三种遍历方法对于左右结点的遍历顺序都是一样的（先左后右），唯一不同的就是根节点的出现位置。对于中序遍历来说，根结点的遍历位置在中间。

所以中序遍历的顺序：左中右

1.1 递归实现

每次递归，只需要判断结点是不是None，否则按照左中右的顺序打印出结点value值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        self.recursive_inorder(root,res)
        return res
    
    def recursive_inorder(self,root,res):
        if root:
            self.recursive_inorder(root.left,res)
            res.append(root.val)
            self.recursive_inorder(root.right,res)
                    
        

1.2 循环实现

循环比递归要复杂得多，因为你得在一个函数中遍历到所有结点。但是有句话很重要：

对于树的遍历，循环操作基本上要用到栈(stack)这个结构

对于中序遍历的循环实现，每次将当前结点(curr)的左子结点push到栈中，直到当前结点(curr)为None。这时，pop出栈顶的第一个元素，设其为当前结点，并输出该结点的value值，且开始遍历该结点的右子树。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        cur=root
        res=[]
        s=[]
        while cur or len(s)!=0:
            while cur:
                s.append(cur)
                cur=cur.left
            if   len(s)!=0:
                cur=s.pop()
                res.append(cur.val)
                cur=cur.right
        return res
                
            
        

二、前序遍历

按照上面的说法，前序遍历指根结点在最前面输出，所以前序遍历的顺序是：中左右

后序遍历指根结点在最后面输出，所以后序遍历的顺序是：左右中

2.1 递归实现

递归实现与中序遍历几乎完全一样，改变一下打印的顺序即可：

class Solution:
    def preorderTraversal(self, root):  ##前序遍历
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return [] 
        return  [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)
        

2.2 循环实现

仍然使用栈stack，由于前序遍历的顺序是中左右，所以我们每次先打印当前结点curr，并将右子结点push到栈中，然后将左子结点设为当前结点。入栈和出栈条件（当前结点curr不为None时，每一次循环将当前结点curr入栈；当前结点curr为None时，则出栈一个结点）以及循环结束条件（整个循环在stack和curr皆为None的时候结束）与中序遍历一模一样。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        cur=root
        res=[]
        s=[]
        while cur or len(s)!=0:
            while cur:
                res.append(cur.val)
                s.append(cur)
                cur=cur.left
            if   len(s)!=0:
                cur=s.pop()
                cur=cur.right
        return res
                        

三、后序遍历

3.1 递归实现

后序遍历指根结点在最后面输出，所以后序遍历的顺序是：左右中

 def postorderTraversal(self, root):  ##后序遍历
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return [] 
        return  self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]

3.2 循环实现

后序遍历中要保证左孩子和右孩子都已经被访问过并且左孩子在右孩子之前访问才能访问根节点。

要保证根节点在左右子树访问之后才能访问因此对于任意节点cur,先将其入栈。

1、如果cur不存在左孩子和右孩子则直接访问。

2、如果cur存在左孩子或者右孩子，但是左孩子或右孩子都已经被访问过了。

同样可以访问该节点，所以可以引入一个pre节点，存储前一次访问的节点。

如果不是上面的两种情况，则将cur的右孩子入栈

再将cur的左孩子入栈（一定要现将右孩子入栈）