94.E 二叉树的中序遍历

Problem: 94. 二叉树的中序遍历

思路

思路1：递归。

思路2：迭代法。

• 从root开始遍历，只要root不为空，就把root入栈，同时让root指向root.next。

• 栈顶节点出站，把值添加到返回结果中。

• 把root赋值为栈顶节点的右子节点。

Code

代码1：

func inorderTraversalV1(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	ans := inorderTraversalV1(root.Left)
	ans = append(ans, root.Val)
	ans = append(ans, inorderTraversalV1(root.Right)...)
	return ans
}

代码2：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	var ans []int
	var stack []*TreeNode
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}

		root = stack[len(stack)-1]
		ans = append(ans, root.Val)
		stack = stack[0 : len(stack)-1]
		root = root.Right
	}

	return ans
}