二叉树的中序遍历golang版本

二叉树的中序遍历golang版本

一种是递归的方式，一种是通过定义stack也就是栈数据结构 stack := make([]*TreeNode,0). 这里的解决思路，就是把左子树上所有节点都放到stack中，因为中序遍历是先来左子树，再来右子树，所以，处理完左子树，就搞右子树，并且是在循环里面，所以左子树循环追加进去的值，要不断的取出，放到输出结果里，并且左边搞完，搞右边，stack，并且是从小的二叉树，到大的二叉树，虽然树的层数不同，但是每次都在for循环的时候，把左子支右子支都穷尽了

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

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

func inorderTraversal(root *TreeNode) []int {
	valueList := make([]int, 0)
	stack := make([]*TreeNode, 0)
	curNode := root
	for curNode != nil || len(stack) > 0 {
		for curNode != nil {
			stack = append(stack, curNode)
			curNode = curNode.Left
		}
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		valueList = append(valueList, top.Val)
		curNode = top.Right
	}
	return valueList
}

func inorderTraversal(root *TreeNode) []int {
	valueList := make([]int, 0)
	if root == nil {
		return valueList
	}
	inorderTraversal(root.Left)
	valueList = append(valueList, root.Val)
	inorderTraversal(root.Right)
	return valueList
}