[数据结构与算法]（四）二叉树深度优先遍历的迭代实现

二叉树的深度优先遍历（前中后序）的迭代实现

0. 递归的本质

想象这么个问题， 要求出 f(3)的结果：
但是求f(3)， 就得先知道 f(2)，那 f(2) 怎么求，当然得知道 f(1) 是啥…

这样最先求的数， 在最后才能得到输出； 也即最先的输入， 在最后输出；
看到这里， 应该想到栈的概念；

此时， 最先的输入 f(3) 便是在 栈底， 后面的输入依次往上，
从而到达栈顶， 也即满足了递归的终止条件；

在递归返回的过程， 便是从 栈顶 到 栈底的 返回过程；

递归的本质实现，是隐性使用了操作系统中的栈；

在每一层递归中， 都会将当前递归层中的函数的局部变量， 参数值，返回前一层的地址 保存起来，压入到栈中；

当递归遇到终止条件时， 开始从栈顶返回到栈底；

那么我们可以使用栈的 方式，来模拟出 递归过程， 从而便诞生了使用 栈迭代实现 深度优先遍历；

1. 深度优先遍历的 迭代实现（框架不统一）

里面有个 最基本的概念，
stack :栈中 是存放的各个 树节点；
result : 结果集中 存放的是 节点中的数值；

1.1 前序遍历的迭代实现

开始， 步骤一：

step2:

步骤三：

步骤四：

步骤五：

步骤：
0. 若传入的根节点是空， 则返回；
１．首先将根节点入栈；
２．只要栈中不为空，开始循环迭代：　
　　2.1 从栈中取出一个节点作为当前节点
　　2.2 将当前节点中的数值，加入到结果列表中保存起来；
　　2.3 若弹出节点的右子树不为空， 则将当前节点的右子树节点加入到栈中；
　　2.4 若弹出节点的左子树不为空， 则将当前节点的左子树节点加入到栈中；

注意， 这里的入栈顺序， 是先将右子树入栈，再将左子树入栈，
从而出栈的时候， 先出左子树，在出右子树， 这样才能满足前序遍历， 保存当前节点， 左子树节点，右子树节点中的数值；

def preOrderTraversal(root: TreeNode) -> list:
    if root == None:
        return

    stack = [root] #  创建一个栈， 并将根节点首先加入其中；
    result = []  #  新建一个列表，保存前序的输出结果；
    while stack:    # 当栈中还有元素时， 就遍历；
        cur_Node = stack.pop()    # 弹出栈顶元素，也即最右边的元素；
        result.append(cur_Node.val)

        if cur_Node.right != None:
            stack.append(cur_Node.right)
        if cur_Node.left != None:
            stack.append(cur_Node.left)
    return  result

1.2 后序遍历的迭代实现

注意到，在前序遍历中，
当前节点数值保存到结果集中后，
往栈中存储节点时， 先存储的右子树节点； 然后存储左子树节点；
这样栈中，弹出元素时， 才是先左 后 右；
然后，结果集中的 存储顺序便是， 中， 左，右；

那么，注意到，在后序遍历中，
当前节点数值保存到结果集中后，
往栈中存储节点时， 先存储的左子树节点； 然后存储右子树节点；
这样栈中，弹出元素时， 才是先右 后 左；
然后，结果集中的 存储顺序便是， 中， 右，左；
最后， 对结果集 进行反转： resutl[::-1]

切片的格式 [0:3:1]，
其中下标0 指的是序列的第一个元素(左边界)，
下标3可以指是切片的数量(右边界), 切片不包括右边界下标。;
[ : ]表示获取序列所有的元素。

参数1表示切片的步长为1，，省略步长则会默认步长为1, 如果是 :-1则表示从右边开始进行切片且步长为1。

def  postOrderTraversal(root:TreeNode)-> list:
    if root == None:  # 若传入的节点为空， 则返回
        return

    stack = [root]
    result = []  # result 中存储节点的最终顺序，需要满足， 左，右，中；
    while stack:
        cur_node = stack.pop()  #  弹出栈顶的元素， 最右边元素,  作为当前节点；
        result.append(cur_node.val)   # result 先存储当前节点；

        if cur_node.left != None:   #  2. 处理中间节点的左子树， 让左节点入栈
            stack.append(cur_node.left)
        if cur_node.right != None:
            stack.append(cur_node.right)  # 3. 再处理中间节点的右子树， 让右节点入栈；
        # 出栈时， 右子树先出栈， 加入到 result 中
        # 从而result 中保存的顺序是 中，右，左， 再将result 从而往前反转一下， 得到 左右中；

    result = result[::-1]
    return  result

1.3 中序遍历的迭代实现

迭代循环中的关键点：

1. 往栈中压入当前节点后，
   当前节点更新为当前节点的左子树节点；
   { 注意到这里的当前节点 只会是两种性质的节点（中间节点， 左子树）的交替出现}

2. 从栈中弹出节点，作为当前节点：
   往结果集中保存了当前节点的数值值后；
   当前节点更新为当前节点的右子树；
   { 注意此时，
   当前节点的性质是 中间节点时， 会更新为右子树节点 。
   当前节点的性质为 左子树节点时，则不存在当前节点的右子树，则从栈中重新弹出一个节点的性质便是中间节点；}

def inOrderTraversal(root: TreeNode) -> list:
    if root == None:
        return  []

    stack = []
    result = []
    cur_Node = root

    while cur_Node or stack:    #  只要当前节点不为空节点， 或者 栈中还有节点时；
        if  cur_Node:               # 只要当前节点不为空， 说明 还没有达到叶子节点
           stack.append(cur_Node)  # 先往栈中，存储中间节点和左子树节点；
           cur_Node = cur_Node.left  # 更新当前节点

        else:        #  当到达最底层节点后， 开始从栈中弹出节点， 往结果集中 存入数值；
            cur_Node = stack.pop()  # 最先弹出的是 叶子节点
            result.append(cur_Node.val)  # 将当前节点的数值保存到结果集中
            cur_Node = cur_Node.right     #  更新当前节点

    return  result

完整的过程：

1. 初始化一个空栈； 初始化时，不将根节点加入到栈中，

2. 初始化一个 空列表， 作为结果集

3. 将根节点赋值为 当前节点；

4. 迭代循环部分， 只要当前节点不为空或者栈不为空：
   第一部分，
   1. 从树的上方到下方，由根节点开始，往栈中存储当前节点；
   2. 将当前节点更新为当前节点的左子树节点， 直到当前节点更新为最底层的叶子节点。

      {注意到此时，栈中只会存储两种性质的节点，
       中间节点和左子树节点 }
   

   第二部分， 开始从栈顶弹出节点：
   0.（由于前面栈中存储节点的性质是，中间节点和 左子树节点）；
   1. 从栈中弹出元素时，先弹出最底层的左子树节点 作为当前节点；
   2. 往结果集中保存当前节点的数值；
   3. 当前节点更新为 当前节点的右子树；

2. 迭代法的 统一框架实现

为什么上述的代码前中后序 三种遍历 方式， 代码框架不能够统一起来呢？

根本原因：
在中序遍历时， 第一次访问到节点时与待处理的节点不统一；
而在 前序遍历中，第一次访问到的节点， 便是要处理的节点；

1. 访问：遍历节点
2. 处理：将元素放进result数组中

因为前序遍历中第一次访问节点（遍历节点）和待处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

实现如何将 访问到的节点 和 待处理的节点， 同步对应起来呢？
此时，便可以，写出三种遍历的 统一框架；

2.0 统一框架的写法- 空指针标记法

方法：
使用标记法， 将要处理的节点放入栈中后， 紧接着放入一个空指针作为标记；
即 将 访问的节点 放入栈中， 要处理的节点也放入栈中，但是处理节点放入栈中后做标记。

注意， 统一框架的三种写法 的规律：

1. 统一的先访问节点： 将节点压入栈中
   遍历所有节点， 让其入栈， 入栈时，注意 中间节点 后面 加一个空指针；
   直到 遍历当前节点变为空节点；

2. 开始处理节点，将节点的数值保存到 结果集中：
   逐个从 栈顶弹出元素， 直到遇到空节点， 则空节点的下一个节点，便是中间节点， 依次将中间节点中的数值保存到 结果集中；

三种 遍历时的顺序：
4. 前序遍历的 结果集中， 保存的顺序是： 中 左 右；
那么 对应的 栈中， 节点入栈的顺序是 右 左 中 空；

5. 中序遍历的 结果集中， 保存的顺序是： 左 中 右；
   那么 对应的 栈中， 节点入栈的顺序是 右 中 空 左；

6. 前序遍历的 结果集中， 保存的顺序是： 左 右 中；
   那么 对应的 栈中， 节点入栈的顺序是 中空 右 左；

2.1 迭代法的 统一框架实现 -标记法

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


import  collections
def levelInputCreateTree(nums: list) -> TreeNode:
    root =  TreeNode(nums[0])  # 将数组首元素 作为根节点；
    que = collections.deque([root])  #  调用 collections 中的 deque, 并且将根节点 输入到其中；

    i, lenNum = 1,  len(nums)  # i 从数组中的下标1开始， 遍历输入到队列中；

    #  迭代法， 创建二叉树
    while i < lenNum:
        cur_Node = que.popleft()  # 弹出双端队列的 左边队首的元素；  该弹出的元素是一个树的节点， 作为当前的节点；

        leftVal, rightVal = nums[i],  nums[i + 1]  if i + 1 < lenNum else -1  #  如果下标 i + 1 超过数组下标， 则赋值为 -1 ；

        if  leftVal != -1 :  #  输入的数组中的 -1 代表此处是 空节点；  或者超出数组下标；
            leftNode = TreeNode(leftVal)  #  将左值 初始化为树的 一个节点；
            cur_Node.left = leftNode  #  将 上述的 左值树节点 赋值为 curNode 的左子树；
            que.append(leftNode)      # 将该节点入队， 便于后序出队， 为他添加子树，也即子节点；

        if  rightVal != -1:
            rightNode = TreeNode(rightVal)
            cur_Node.right = rightNode
            que.append(rightNode)

        i += 2
    return root

def inOrderTraversal(root:TreeNode) -> list:
    stack = []        #   入栈时，   右， 中 空， 左
    result = []       #   结果集，  左 中  右

    if root != None:    #  只有当 根节点不为空时，  根节点压入栈中；
        stack.append(root)


    # 当栈中存在节点时， 开始迭代遍历节点
    while stack:
        cur_Node =  stack.pop()
        if cur_Node != None:      # 因为入栈中的节点，有四种性质， 中间节点，空节点， 左节点， 右节点；  所以出栈时， 也会有四种节点;
            if cur_Node.right != None:
                stack.append(cur_Node.right)

            stack.append(cur_Node)  #  当前节点入栈， 后面紧接一个 None 节点
            stack.append(None)

            if cur_Node.left != None:
                stack.append(cur_Node.left)
        #  此时， 树中的节点以及全部入栈了;
        #  开始从栈顶 弹出元素， 而只有弹出的节点是空节点， 紧接着在弹出一个元素才是，待处理的节点，应该放入到结果集中；
        else: #
            cur_Node = stack.pop()
            result.append(cur_Node.val)

    return  result




def preOrderTraversal(root: TreeNode) -> list:
    stack = []   #   右， 左，  中 标  ，  标是 代表标记节点，  这里使用空节点 作为标记节点；
    result = []  #   中， 左，  右

    if root != None:
        stack.append(root)


    while stack:  #  当栈中有节点时
        cur_Node = stack.pop()  # 从栈中 取出元素， 栈中存放了四种类型的节点；
        if  cur_Node != None:
            if  cur_Node.right != None:          # 右节点压入栈中
                stack.append(cur_Node.right)

            if cur_Node.left  != None:          # 左节点压入栈中；
                stack.append(cur_Node.left)

            stack.append(cur_Node)     #  当前节点压入栈中；
            stack.append(None)         # 标记节点压入栈中；

        else:  # 所有节点已经入栈， 开始从栈顶弹出节点，  当弹出的是空节点， 则再弹出去一个节点才是， 待处理的中间节点， 将中间节点的数值压入到结果集中；
            cur_Node = stack.pop()
            result.append(cur_Node.val)

    return  result










if __name__ == "__main__":
    print("--- please input a  level order list to create A Binary Tree---")
    # strip 去除输入中最左边右边的 空格；  split 将输入按空格分割， 返回一个列表；
    #  map 是将input() 输入的字符串 转换为 int 整型；
    nums = list(map(int, input().strip().split()))
    print("you  level order Tree input list : ", nums)
    # 将输入的 层序 列表 建成树；
    tree1 = levelInputCreateTree(nums)

    # 按照 先序遍历树；
    print(" preorder Traversal the Tree: \n", preOrderTraversal(tree1))

    # 按照 中序遍历树；
    print("\n inorder Traversal the Tree: \n", inOrderTraversal(tree1))
    # 按照 序遍历树；

    # 按照 后序遍历树；
    # print(" \n postorder Traversal the Tree: \n", postOrderTraversal(tree1))

    # 18 7 11 3 4 5 6