使用非递归实现二叉树的遍历

摘要

非递归版本的二叉树中序遍历
- BST是什么
- BST Iterator的两种实现方法

86 · 二叉查找树迭代器

通过实现 hasNext 和 next 两个方法，从而实现二叉查找树的中序遍历迭代器

实现要点

递归 → 非递归，意味着自己需要控制原来由操作系统控制的栈的进进出出
如何找到最小的第一个点？最左边的点即是
如何求出一个二叉树节点在中序遍历中的下一个节点？
在 stack 中记录从根节点到当前节点的整条路径
下一个点=右子树最小点 or 路径中最近一个通过左子树包含当前点的点

          5
        /   \
       3     8
     /   \
    2     4
   /
  1 

stack 5 3 2 1
stack 5 3 4 的时候就是要找路径中最近一个通过左子树包含当前点的点，一直pop

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type BSTIterator struct {
	stack []*TreeNode
}

func NewBSTIterator(root *TreeNode) *BSTIterator {
	iter := new(BSTIterator)
	for root != nil {
		iter.stack = append(iter.stack, root)
		root = root.Left
	}
	return iter
}

func (iter *BSTIterator) HasNext() bool {
	return len(iter.stack) > 0
}

func (iter *BSTIterator) Next() *TreeNode {
	cur := iter.stack[len(iter.stack)-1]
	node := cur
	if node.Right != nil {
		node = node.Right
		for node != nil {
			iter.stack = append(iter.stack, node)
			node = node.Left
		}
	} else {
		iter.stack = iter.stack[:len(iter.stack)-1]
		for iter.HasNext() && iter.stack[len(iter.stack)-1].Right == node {
			node = iter.stack[len(iter.stack)-1]
			iter.stack = iter.stack[:len(iter.stack)-1]
		}
	}
	return cur
}

一种更简单的实现方式

在 stack 中不保存哪些已经被 iterator 访问过的节点
即如果 iterate 到了这个节点，即便右子树还未完全遍历
也从 stack 里踢出

type BSTIteratorSimple struct {
	stack []*TreeNode
}

func NewBSTIteratorSimple(root *TreeNode) *BSTIteratorSimple {
	iter := new(BSTIteratorSimple)
	iter.findMostLeft(root)
	return iter
}

func (iter *BSTIteratorSimple) findMostLeft(node *TreeNode) {
	for node != nil {
		iter.stack = append(iter.stack, node)
		node = node.Left
	}
}

func (iter *BSTIteratorSimple) HasNext() bool {
	return len(iter.stack) > 0
}

func (iter *BSTIteratorSimple) Next() *TreeNode {
	node := iter.stack[len(iter.stack)-1]
	iter.stack = iter.stack[:len(iter.stack)-1]
	if node.Right != nil {
		iter.findMostLeft(node.Right)
	}
	return node
}

总结

如果需要求前继结点，第一种方法更好，只需要 left 换成 right，right 换成 left
第二种方法则做不到，因为已经丢失了节点信息

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。