二叉排序树转为非空的双向链表，非递归实现
class Solution: def Convert(self, pRootOfTree): root=pRootOfTree # 需要判断边界条件:二叉树为空 if not root: return s=[] res=[] s.append(root) node=root.left while s or node: if node: s.append(node) node=node.left else: p=s.pop() res.append(p) node=p.right res_root=res[0] while res: top=res.pop(0) if res: top.right=res[0] res[0].left=top return res_root
按照中序遍历二叉树非递归的方式先中序遍历二叉树，我们必然得到一个有序的list
接下来，就是要对这个有序的list里的每个节点修改他们的左右指针（即原来二叉树里的左右孩子指针）：
我们不断的从数组的索引0位置（即栈底而不是栈顶）出栈元素，这个元素一定是数组里最小的，那么这个元素按照从栈底的位置出栈后，它的right指针应该指向当前栈的栈底，而当前栈的栈底的left指针应该指向它
注意判断边界条件：当栈空时退出循环，且上述操作只能在栈非空时进行，即在循环内还要进行一次栈非空的判断，因为循环体内上述操作之前，先进行了出栈。
投递拼多多集团-PDD等公司10个岗位 >
查看25道真题和解析