算法随笔-二叉树遍历的N种姿势

最近在练习用Python刷算法，leetcode上刷了快300题。一开始怀疑自己根本不会写代码，现在觉得会写一点点了，痛苦又充实的刷题历程。对我这种半路出家的人而言，收获真的很大。

今天就从二叉树遍历写起，曾经有次面试就被迭代实现卡过。。。

最简单的递归

#先序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        def preTraversal(node,result):
            if node==None:
                return
            #输出放在最前
            result.append(node.val)
            preTraversal(node.left,result)
            preTraversal(node.right,result)
        preTraversal(root,res)
        return res

#中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        def inorderTraversal(node,result):
            if node==None:
                return
            inorderTraversal(node.left,result)
            #输出放在中间
            result.append(node.val)
            inorderTraversal(node.right,result)
        inorderTraversal(root,res)
        return res

#后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        def postTraversal(node,result):
            if node==None:
                return
            postTraversal(node.left,result)
            postTraversal(node.right,result)
            #输出放在最后
            result.append(node.val)
        postTraversal(root,res)
        return res

递归实现极其简单，但是面试时往往会更进一步，问几个深入一点的问题：

1. 递归实现存在什么问题？ 
2. 尾递归是什么？

这两个问题都在讲一件事，就是迭代实现的二叉树遍历会存在StackOverflow异常。却决于操作系统和运行时，不同的程序拥有的栈大小不一，但是栈的容量都是较小的，基于递归的实现，如果未优化，就会导致堆栈溢出的异常。对.NET而言，系统分配的默认栈空间大小是1MB，树节点一多，很容就满了。

而尾递归则是对普通递归的优化，每次迭代最后都是直接调用自身。很多编译器都对尾递归做了生成优化，使得它可以不在调用栈上面每次都添加一个新的堆栈帧，而是更新它。这样就不会导致调用栈爆炸的异常。

如果你能答上上面的问题，往往会让你写一下二叉树遍历非递归的实现，这里难度就上了一个台阶。

非递归实现

二叉树迭代一定会用到栈！二叉树迭代一定会用到栈！二叉树迭代一定会用到栈！

talk is easy, show you my code

#超简单的先序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return
        stack=[root]
        while stack:
            node=stack.pop()
            res.append(node.val)
            #栈先进后出，顺序要注意
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

#稍复杂的中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        curr=root
        stack=[]
        while curr or stack:
            #优先遍历全部左节点
            while curr:
                stack.append(curr)
                curr=curr.left
            node=stack.pop()
            res.append(node.val)
            #当前节点切换到右节点
            if node.right:
                curr=node.right
        return res

#最复杂的后序遍历
#解法1 基于先序遍历的变形  leetcode官方题解：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/

def postorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return res
        stack=[root]
        while stack:
            node=stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        #反转结果
        return res[::-1]

#解法2 记录走过的路径
def postorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return res
        stack=[root]
        km=set()
        while stack:
            node=stack[-1]
            #只有叶子节点和左右节点被遍历过的才可以输出
            if (node.left==None and node.right==None) or (node.left in km or node.right in km):
                res.append(node.val)
                km.add(node)
                stack.pop()
            else:
                #注意进栈顺序
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        return res

#解法3 中序遍历的变形,左右子树遍历切换
def postorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return res
        stack=[]
        curr=root
        last=None
        while curr or stack:
            if curr:
                stack.append(curr)
                #切换到左子树
                curr=curr.left
            else:
                node=stack[-1]
                #是否切换到右子树
                if node.right and node.right!=last:
                    curr=node.right
                else:
                    res.append(node.val)
                    stack.pop()
                    last=node
        return res

后序遍历的几种迭代解法非常值得一看，想起当初在白板面前呆了半天也没写出来，蓝廋香菇，现在可以自信地讲树的遍历我掌握了！！！