思路

1. 我应该是比较少见的，用迭代做的吧~
2. 在迭代应用上，我选择了统一方法【详情看 代码随想录 - 二叉树迭代的统一解法】，也就是遍历与节点操作分离，操作思路如下：
   1. 首先，我在注入 stack 时观察到，其实没有输出 list 的需求，那注入的时候就不需要改为 “倒序”，反而 “左中右” 的格式是适合的题目要求的；
   2. 在操作里，我记录了节点最后一个输出，以完成双向连接，相比申请全局变量的解法，这样做更加安全；
   3. 此外，还有一些细节
      1. 由于使用 stack, 需要考虑 尾部 上的节点关系情况
      2. 空节点 和 题目要求 的 return 值
3. 复杂度分析
   1. 时间复杂度包括 遍历 和 处理 两个环节，是 $O(n)O(n)$，较真比较递归的复杂度情况，我认为是少于的，因为 不用 回弹保存的函数和变量，处理操作数是一样的；
   2. 空间复杂度：题目应该说额外空间使用率；总的来说是迭代肯定低于递归了；

代码

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

#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:
    def Convert(self , pRootOfTree ):
        # write code here
        
        def miniConvert(pRootOfTree) -> TreeNode:
            if not isinstance(pRootOfTree, TreeNode): return []

            cur = pRootOfTree
            # if not cur: return cur

            stack = [cur]
            next = None
            while stack:
                cur = stack.pop()
                if cur:
                    if cur.left: stack.append(cur.left)
                    stack.append(cur)
                    stack.append(None)
                    if cur.right: stack.append(cur.right)
                else:
                    cur = stack.pop()
                    # 节点处理
                    if next:  
                        next.left = cur
                        cur.right = next
                    else:
                        cur.right = next
                    next = cur
            return cur
          
        cur = miniConvert(pRootOfTree)
        if not cur: return 
        while cur.left:
            cur = cur.left
        return cur