【二叉树】leetcode94——二叉树的中序遍历

编号94：二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

思路

具体代码如下：

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

• 递归算法

/*递归三部曲
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
*/

//1.确定递归函数的参数和返回值：因为要打印出中序遍历节点的数值，所以参数里传入[]int类型
//不需要有返回值
func traversal(root *TreeNode, result *[]int) {
	//2.确定终止条件
	if root == nil {
		return
	}

	//3.确定单层递归的逻辑
	//中序遍历 是 左 中 右 的顺序
	traversal(root.Left, result)        //左
	*result = append(*result, root.Val) //中
	traversal(root.Right, result)       //右
}

func inorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	traversal(root, &result)
	return result
}

• 迭代算法

  中序遍历的迭代算法和前序遍历，后序遍历都不同。因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，「因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。」

  那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了「处理顺序和访问顺序是不一致的。」

  那么「在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。」

  这里引入了公众号代码随想录的gif动画，方便理解：

  

func inorderTraversal(root *TreeNode) []int {
	stack := make([]*TreeNode, 0) //存放二叉树节点
	result := make([]int, 0)      //存放节点数值

	for root != nil || len(stack) != 0 {
		if root != nil {
			//将当前节点存入栈
			stack = append(stack, root)
			root = root.Left //左  一直访问到最左边的节点
		} else { //说明到达了二叉树的最底部
			//从栈中取出当前节点
			root = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			//遍历节点的数值
			result = append(result, root.Val) //中
			root = root.Right                 //右
		}
	}

	return result
}

【二叉树】leetcode94——二叉树的中序遍历

原文：https://www.cnblogs.com/zmk-c/p/14492634.html