leetcode 94. 二叉树的中序遍历

题目描述

给定一个二叉树,返回它的中序 遍历。

示例:


输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

题解

通过stack模拟栈进行中序遍历

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
stack := make([]*TreeNode, 0)
for root != nil || len(stack) != 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return res
}