二叉树的中序遍历｜Java 开发实战-一一网

题目一

leecode 94. 二叉树的中序遍历

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

图片.png

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

参考代码

定义一颗树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int          // 根
 *     Left *TreeNode   //左节点
 *     Right *TreeNode  //右节点
 * }
 */
复制代码

GO语言版 递归

func inorderTraversal(root *TreeNode) (res []int) {
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return // 结束当前递归
		}
		inorder(node.Left) // 直接怼到左边最下边
		res = append(res, node.Val) // 添加到数组里
		inorder(node.Right) // 看右边还有没有分支，有就继续走，没有就将右节点加入数组
	}
	inorder(root)
	return
}

复制代码

GO语言版 迭代栈：先进后出

定义一个栈，栈存的就是一棵树

1.先将整颗树怼进去，在把所有的左子树怼进去

2.遍历左子树，直接左边的最下边

3.因为先进后出，拿到了最下面的左节点

4.怼到数组里

5.看以右节点为根的还有没有左节点，有就回到上面第1步，没有就走第3步，把根节点怼进去，在怼右节点。

func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}    // 定义一个栈，栈存的就是一棵树
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)  // 1.先将整颗树怼进去，在把所有的左子树怼进去
			root = root.Left   // 2.遍历左子树，直接左边的最下边
		}
		root = stack[len(stack)-1]  // 3.因为先进后出，拿到了最下面的左节点
		stack = stack[:len(stack)-1]
		res = append(res, root.Val) // 4.怼到数组里
                //5.看以右节点为根的还有没有左节点，有就回到上面第1步，没有就走第3步，把根节点
		root = root.Right // 
	}
	return
}

复制代码