本文主要综述了二叉树的三种遍历方式及相关的leetcode算法问题的解法。
线性数据结构(矩阵、列表、队列、堆栈) )不同，树的遍历可以有不同的遍历方式。
先序遍历排线流程如下。
访问根节点，访问当前节点的左子树，访问当前节点的右子树。 顺序扫描的应用场景主要是复制树。 在上树中，第一次扫描的顺序是1 2 4 5 3。
让我们简单地递归实现：
defprintpreorder(root ) : if root : print (root.val )，print preorder (root.left ) print preorder (root.rt.right )
访问左侧的子树，访问根节点，访问右侧的子树。 中顺序遍历的应用场景主要位于二叉搜索树上。 这是因为返回的节点值会增加。 通过变形中继导线，也可以返回减少的BST值。 在上面的示例中，中顺序扫描的顺序应该是42513。
efprintinorder(root ) : if root : print in order (root.left ) print )、print in order (root.right ) )
94.binarytreeinordertraversal (https://leet code-cn.com/problems/binary-tree-in order-traversal/)
用堆栈的方法做：
efinordertraversal(root ) :RES=[]node_stack=[] p=rootwhilepornode _ stack 3360 whilep : stack.append ) ) ) ) p=p.left cur _ node=node _ stack . )
95.binarysearchtreeiterator (https://leet code-cn.com/problems/binary-search-tree-iterator/)，这个问题的解决方法其实也是使用堆栈
因为主题是相关的，所以在这里简单地提到迭代器的概念：
迭代是Python最强大的功能之一，是访问集合元素的一种方法。
迭代器是可以记住导线测量位置的对象。
迭代器对象是从集合中的第一个元素开始访问的，直到所有元素都被访问完。 迭代器不能向前下降。
迭代器有两种基本方法： iter (和next )。
可以使用字符串、列表或元组对象创建迭代器
有关详细定义和示例，请参见https://www.run OOB.com/python3/python3- iterator-generator.html
中序遍历排线流程如下。
访问左侧的子树，访问右侧的子树，访问根节点。 遍历可用于删除树。 上面的例子是按照后面的顺序进行遍历的正确顺序是4 5 2 3 1。
defprintpostorder(root ) : if root : print postorder (root ) root.val ) root.left (print postorder ) root (rt )
binarytreepostordertraversal (https://leet code-cn.com/problems/binary-tree-postorder-traversal/)
解决方法如下。 defpostordertraversal(root ) : if not root 3360 return [ ] RES=[ ] node _ stack=[ root ] while node _ stack 3360 node ) if node.left : node _ stack.append (node.left ) if node.right 3360 node _ stack.append (node.right ) RES.append
在树的深度优先遍历(包括前、中、后遍历)中，递归方法最直观易懂，但考虑到效率，通常不推荐递归。
堆栈方法虽然可以提高效率，但其嵌套循环非常烫手，难以理解，容易造成“一看就知道，但一写就废”的困境。 另外，循环结构根据扫描顺序(前序、中序、后序)的不同而有很大差异，给记忆增加了负担。
因此，我们将结合堆栈迭代方法的效率，介绍像递归方法一样简洁易懂的“颜色标记法()。 此外，该方法可以为前序、中序、后序的迭代编写完全一致的代码。
其核心思想如下
使用颜色标记节点的状态。 新节点为白色，访问的节点为灰色。
如果找到白色节点，请将其标记为灰色，然后按右侧子节点、自身和左侧子节点的顺序进行堆栈。
如果检测到的节点为灰色，则输出节点值。
使用该方法实现的中顺序扫描如下： 为了实现前后遍历，只需调整左右子节点的堆栈顺序即可。
类解决方案3360 definordertraversal (self，root: TreeNode )- List[int]: WHITE，gray=0，1 RES=[ ] stack=[ node=stack.pop ) ifnodeisnone : continue if color==white3360stack.append ) ) white 3360 stack.append ) ) 652 non node ) ) ) stack.append ) ) white，node.left () (else:RES.append ) node.val )将原始链接附加到return res。 https://leet code-cn.com/problems/binary-tree-inor REE-in