前序遍历
前序遍历是先遍历根节点，然后遍历左子树，最后遍历右子树
rst.append(node.Val)
preorder(node.Left)
preorder(node.Right)
改写成迭代，压栈右节点
for{
if node == nil && stack == nil
return
if node == nil
node = stack.pop()
if node.Right != nil {
stack.push(node.Right)
}
rst.append(node.Val)
node=node.left
}
中序遍历
前序便利是先便利左子树，然后遍历根前节点，最后遍历又子树，根据这个性质，对于二叉搜索树来说，中序遍历的结果是单调递增的。
inorder(node.Left)
rst.append(node.Val)
inorder(node.Right)
迭代还是使用栈的结构，先压栈根节点，然后从栈中取出根节点便利，并将根节点的右节点设置为下一个要遍历的节点。
for{
if node == nil && stack == nil
break
if node == nil
tmp == stack.pop
rst.append(tmp.Val)
node =tmp.right
continue
stack.push(node)
node=node.Left
}
后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后再遍历当前节点
inorder(node.Left)
inorder(node.Right)
rst.append(node.Val)
迭代实现，后序遍历的迭代实现相较于前序和中序不太一样，只有当这个节点没有叶子节点，或者这个节点是从右节点返回时，我们才访问这个节点，所以，参考中序遍历，并且规定只有在弹栈的时候，我们才访问节点
- 初始设置上一个节点为 nil，压栈根节点，访问左子树
- 当节点为空时，从栈上弹出其父节点作为当前节点，此时如果上一个节点等于该节点的右节点（上一个节点可能为空），则访问父节点（输出），并更新前一个节点为当前节点，否则我们访问当前节点的右节点。
for{
if node == nil && stack == nil
break
if node == nil
node = stack.pop()
if pre=node.Right || node.Right == nil // IMPORTANT
rst.append(node.val)
pre = node
node=nil
continue
else
stack.push(node)
node = node.right
continue
stack.push(node)
node = node.Left
}
这里标注 IMPORTANT 的判断很重要，如果不加 node.Right == nil 的判断，因为存在右节点为空的情况，当我们正常从左节点返回时，本来应该遍历右子树，然后更新 pre，结果右节点为空，导致回到父节点，然后又去遍历左子树，无线循环下去。
一以贯之
前边的三种遍历看似简单，其实还是相当混乱，思路完全不统一，受后序遍历的启发，我觉得可以找到一种通用的遍历方法。
- 一个栈，这个栈保留的是从根节点到当前节点的路径
- 一个指针，指示是从哪个节点返回的，并应该跳转到哪个节点
- 最后根据这个指针，判断应该在什么情况下输出
在三种遍历里，1,2 是完全相同的
- 对于1，以深度优先的方式，先遍历左子树，再遍历右子树
- 对于2，当从左节点返回时，应该去遍历右节点，当从右节点返回时，应该跳转到上一节点
唯一不同的是 3，即什么时候输出的问题
前序遍历，压栈之前就输出，即第一次访问就输出
中序遍历，弹栈的时候，从左节点返回时输出
后序遍历，弹栈的时候，从右节点返回时输出
前序遍历
func preorderTraversal(root *TreeNode) []int {
node := root
stack:=make([]*TreeNode, 64)
i:=0
var rst []int
var pre *TreeNode
for {
if node == nil && i == 0 {
break
}
if node == nil {
node = stack[i-1]
i--
if pre == node.Right {
pre = node
node = nil
continue
}else {
pre = nil
i++
node = node.Right
continue
}
}
////////////////////////////////////////////////////////////
rst=append(rst, node.Val)
////////////////////////////////////////////////////////////
stack[i] = node
i++
node=node.Left
}
return rst
}
中序遍历
func inorderTraversal(root *TreeNode) []int {
node := root
stack:=make([]*TreeNode, 64)
i:=0
var rst []int
var pre *TreeNode
for {
if node == nil && i == 0 {
break
}
if node == nil {
node = stack[i-1]
i--
////////////////////////////////////////////////////////////
if pre == node.Left {
rst=append(rst, node.Val)
}
////////////////////////////////////////////////////////////
if pre == node.Right {
pre = node
node = nil
continue
}else {
pre = nil
node = node.Right
i++
continue
}
}
stack[i] = node
i++
node=node.Left
}
return rst
}
后序遍历
如果节点是从右节点返回的，输出，这里因为存在右节点为空时，不从右节点返回的情况，所以额外的，当右节点为空时，我们也访问这个节点，然后跳到这个节点的上一个节点。
func postorderTraversal(root *TreeNode) []int {
node := root
stack:=make([]*TreeNode, 64)
i:=0
var rst []int
var pre *TreeNode
for {
if node == nil && i == 0 {
break
}
if node == nil {
node = stack[i-1]
i--
////////////////////////////////////////////////////////////
if pre == node.Right {
rst=append(rst, node.Val)
}
//////////////////////////////////////////////////////////
if pre == node.Right {
pre = node
node = nil
continue
}else {
pre = nil
i++
node = node.Right
continue
}
}
stack[i] = node
i++
node=node.Left
}
return rst
}
可以看到，整个代码除了引起来的用于输出的地方外，整个逻辑结构完全一致。在思考这个代码结构期间，修改调试了好几次，总算是找到了通用的实现结构。
一个很重要的点是，如果是从左节点跳到右节点，需要设置上一个节点为 nil，这样，右子树的第一个要输出的节点才能正确的进行 pre == node.Right 的判断，并更新后续 pre。
网友评论