题目

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

示例:

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

方案一（递归）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ret := []int{}
    if root != nil {
        ret = append(inorderTraversal(root.Left), root.Val) // 首先遍历左子节点，然后遍历当前节点
        ret = append(ret, inorderTraversal(root.Right)...) // 最后遍历右子节点
    }

    return ret
}

面向对象设计：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.li = []
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return self.li

        self.inorderTraversal(root.left)
        self.li.append(root.val)
        self.inorderTraversal(root.right)
        return self.li

方案二（迭代）

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    visited := map[*TreeNode]bool{} // 是否已遍历
    stack := []*TreeNode{root}
    ret := []int{}
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if _, ok := visited[node]; ok {
            ret = append(ret, node.Val)
            continue
        }
        if node != nil {
            visited[node] = true
            stack = append(stack, node.Right)
            stack = append(stack, node)
            stack = append(stack, node.Left)
        }
    }

    return ret
}

不需要 **visited** 的迭代：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        # 用p当作指针
        p = root
        while p or stack:
            # 把左子树压入栈中
            while p:
                stack.append(p)
                p = p.left
            p = stack.pop()
            res.append(p.val)
            p = p.right
        return res

原文

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/2/