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

二叉树面试非递归前序遍历

算法

发布日期: 2024-04-04

更新日期: 2024-04-05

文章字数: 500

阅读时长: 2 分

阅读次数:

写在前面

上一篇文章面试题：二叉树的非递归中序遍历介绍了非递归中序遍历，举一反三，本文来介绍一下非递归前序遍历。

写完非递归前序遍历后发现，思路和代码根非递归中序遍历差不多，代码相似度高达90%，先看代码

代码

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

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 TreePreVisit1(root *Node) []int {
	if root == nil {
		return nil
	}
	if root.Left == nil && root.Right == nil {
		return []int{root.Val}
	}
	result := []int{root.Val}
	result = append(result, TreePreVisit1(root.Left)...)
	result = append(result, TreePreVisit1(root.Right)...)
	return result
}

// 二叉树的非递归前序遍历
func TreePreVisit(root *Node) []int {
	result := []int{}
	// 1.定义一个栈
	s := newStack()
	p := root
	for true {
		for p != nil {
			// 访问栈顶元素
			result = append(result, p.Val)
			// p入栈
			s.push(p)
			p = p.Left
		}
		// 从栈顶出战
		if s.empty() {
			break
		}
		p = s.pop()

		// 指向右孩子
		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
}

代码根中序的相比较发现只有一点点区别。前序和中序算法思路都是一样的，都是访问父节点和入栈。唯一区别是这两个步骤的先后顺序不一样。