94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3] 1 2 / 3 Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
思路：
二叉树的中序遍历，先访问左子树然后中间节点然后右子树。迭代也是使用list容器来充当栈
代码：
go ：
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// recursive
/*func inorderTraversal(root *TreeNode) []int {
var res []int
recursive(root, &res)
return res
}
func recursive(root * TreeNode, res *[]int) {
if root == nil {
return
}
recursive(root.Left, res)
*res = append(*res, root.Val)
recursive(root.Right, res)
}
*/
// iteratively
func inorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
cur := root
for cur != nil || len(stack) != 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
// 走到最左
cur = stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
res= append(res, cur.Val)
cur = cur.Right
}
return res
}
