面试题：二叉树的非递归中序遍历

写在前面

最近面试遇到这个算法题，其实二叉树的前序、中序、后续非递归算法是最基本的、必须掌握的算法。但是这个题目花了我40分钟时间，实在不应该，今天总结一下，希望下次能记住。

思路

二叉树的中序遍历，其实就是左-》中-》右，先访问左孩子，然后访问父节点，说明一定要将父节点先保存起来，后面再访问。

当访问了左孩子，紧接着访问父节点的时候，如何找到父节点呢？我们无法通过类似于pre变量将父节点保存起来，因为父节点访问完了还要找它的父节点。

通过画几个示例，我们会发现刚刚访问的左孩子的父节点其实就是指针刚刚经过的那个节点。即指针找到左孩子的时候，前一个节点就是它的父节点，现在问题转换成：访问刚刚经过的那个节点。显然，这是栈的思维，后进先出。

因此，需要用到栈，将一路经过的节点先入栈

代码

定义节点的结构

// 定义节点
type Node struct {
	Val         int
	Left, Right *Node
}

// 二叉树的非递归中序遍历
func TreeMidVisit(root *Node) []int {
	result := []int{}
	// 定义一个栈
	s := newStack()
	p := root
	for true {
		for p != nil {
			// p入栈
			s.push(p)
			p = p.Left
		}
        // 此时p=nil
        // 如果栈为空，则退出
		if s.empty() {
			break
		}
		// 从栈顶出栈
		p = s.pop()
		// 访问栈顶元素
		result = append(result, p.Val)
		// 指向右孩子
		p = p.Right
	}

	return result
}

题目中用到了栈，因此定义一个栈

// 定义一个栈
type stack struct {
	data []*Node
	top  int
}

func newStack() *stack {
	return &stack{
		data: make([]*Node, 100), // TODO 先假设所有节点数量小于100
		top:  -1,
	}
}

func (s *stack) push(node *Node) {
	s.top++
	s.data[s.top] = node
}

func (s *stack) pop() *Node {
	if s.empty() {
		return nil
	}
	node := s.data[s.top]
	s.top--
	return node
}

func (s *stack) empty() bool {
	return s.top == -1
}

下面写一下测试用例

先根据数组生成二叉树

func NewTree(data []int) *Node {
	n := len(data)
	if n == 0 {
		return nil
	}
	if n == 1 {
		return &Node{Val: data[0]}
	}

	nodes := make([]*Node, 0, n)
	for i := range data {
		if data[i] == 0 {
			// TODO 假设0表示空节点
			continue
		}
		tmpNode := &Node{
			Val: data[i],
		}

		if i == 0 {
			// 第一个节点
			nodes = append(nodes, tmpNode)
			continue
		}

		parentIdx := (i - 1) / 2
		if i%2 == 1 {
			// 左孩子
			nodes[parentIdx].Left = tmpNode
		} else {
			// 右孩子
			nodes[parentIdx].Right = tmpNode
		}
		nodes = append(nodes, tmpNode)
	}
	return nodes[0]
}

为了验证结果的正确性，写一个中序遍历递归算法

// 递归
func TreeMidVisit1(root *Node) []int {
	if root == nil {
		return nil
	}
	if root.Left == nil && root.Right == nil {
		return []int{root.Val}
	}
	result := TreeMidVisit1(root.Left)
	result = append(result, root.Val)
	result = append(result, TreeMidVisit1(root.Right)...)
	return result
}

下面是2个测试用例

func main() {
	testCases := []TestCase{
		{
			data: []int{1, 2, 3, 4, 5, 6, 7},
		},
		{
			data: []int{1, 2, 3, 0, 4, 5, 0},
		},
	}

	for i := range testCases {
		begin := time.Now()
		root := NewTree(testCases[i].data)
		result := TreeMidVisit(root)
		result1 := TreeMidVisit1(root)
		fmt.Printf("i:%d,result:%v,递归结果：%v,time cost:%f\n", i, result, result1, time.Since(begin).Seconds())
	}
}

type TestCase struct {
	data []int
	want int
}

结果

i:0,result:[4 2 5 1 6 3 7],递归结果：[4 2 5 1 6 3 7],time cost:0.000007
i:1,result:[2 4 1 5 3],递归结果：[2 4 1 5 3],time cost:0.000002

总结

二叉树中序非递归算法其实很简单，可以死记一下：

• 从根节点出发，一直往左，入栈
  弹出栈顶元素，访问，指向右孩子，继续第一步。