Python递归和迭代解二叉树前序，中序，后序遍历

题目：二叉树的前序，中序，后序遍历

前序关键词：根左右

中序关键词：左根右

后序列关键词：左右根

---

题目来源Leetcode：

前序遍历

中序遍历

后序遍历

---

代码：

前序：

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None
		 
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

        # 递归算法
        if root is None:
             return []
        result = [root.val]
        # 从底层网上追加
        result.extend(self.preorderTraversal(root.left))
        result.extend(self.preorderTraversal(root.right))
        return result


        # 迭代算法，栈+DFS
        if root is None: # 如果该结点为空
            return []
        stack = []       # 初始化一个栈
        results = []     # 初始化结果队列
        while stack or root:      # 当栈空且结点遍历完则跳出循环
            if root:              # 当前结点存在，先遍历左子树
                results.append(root.val)         # 将值添加到结果队列
                stack.append(root)               # 将该结点压入栈
                root = root.left                 # 指向其左孩子结点
            else:                 # 结点不存在需要遍历右子树
                root = stack.pop()               # 从栈中弹出每个子数的根结点
                root = root.right                # 指向其右孩子结点
        return results

---

中序：

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # # 递归
        if root is None:
             return []
        result = []
        result.extend(self.inorderTraversal(root.left))
        result.extend([root.val])
        result.extend(self.inorderTraversal(root.right))
        return result

        # 迭代算法，栈+BFS
        if root is None:
            return []
        result = []
        stack = []
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                result.append(root.val)
                root = root.right
        return result

---

后序：

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 递归算法
        if root is None:
             return []
        result = []
        result.extend(self.postorderTraversal(root.left))
        result.extend(self.postorderTraversal(root.right))
        result.extend([root.val])
        return result

        # 迭代算法
        if root is None:
            return []
        stack = []          # 栈
        result = []          # 结果列表
        temp = None    # 记录上一次已经访问过的结点
        while stack or root:
            if root:
                stack.append(root)
                root = root.left    # 指向左结点
            else:
                root = stack[-1]   # 这里先不出栈，获取栈顶元素，因为是左右根顺序
                if root.right and root.right != temp:      # 右孩子存在且未被访问过，防止死循环，要判断是否已经访问过一次
                    root = root.right   # 指向其右孩子结点
                    stack.append(root)  # 将右孩子结点入栈
                    root = root.left    # 指向其左孩子结点，再次遍历其左子树
                else:
                    root = stack.pop()          # 出栈，右子树已经全部访问过或已没有右孩子结点
                    result.append(root.val)  # 添加到结果列表中
                    temp = root                   # 该结点出栈，意味着已经访问过一次，防止死循环， 防止右孩子循环
                    root = None                  # 此时应该出栈的是子树的根结点，因此需要满足回退的时候不会再去访问左子树, 防止根节点循环
        return result

---

总结：

对于三种顺序的二叉树遍历，递归算法从思想上和代码量上来说要比迭代简单写，但是递归所开辟的空间和效率一定程度上高于迭代。

做这篇笔记的主要目的是学习二叉树遍历的迭代算法和递归算法思想的区别。

递归算法：思路还是蛮简单的，只要结合画图，可以很轻松的理清头绪。

迭代算法： 需要借助栈或者队列临时保存数据，因此增加了变成的复杂度，但一定程度上提高了遍历的效率，锻炼了思维。

---

最后说下后序的迭代算法，后序迭代算法中需要注意的是，当遍历完左子树后，不能像先序和中序那样直接将根结点出栈，因为后序是左右根，判断完左边，还需要判断右边，最后才会输出根结点。而且细想以下，又出现了一个问题，遍历右子树，同样按照左右根的顺序遍历下去，那么一轮下来肯定是所有结点都会遍历结束，此时就需要像递归那样回退，只不过迭代中借助出栈来实现回退，那么回退的过程中肯定会回到当初遍历过得某个根结点，如果不对该根结点做标识，则会导致死循环。因此还需要添加一个标志位，表示该结点刚才已经被访问过一次。