> For the complete documentation index, see [llms.txt](https://rachel2011.gitbook.io/leetcode_cc150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rachel2011.gitbook.io/leetcode_cc150/binary-tree/binary-tree-inorder-traversal.md).

# Binary Tree Inorder Traversal

Given a binary tree, return theinordertraversal of its nodes' values.

For example:\
Given binary tree`[1,null,2,3]`,

```
   1
    \
     2
    /
   3
```

return`[1,3,2]`.

**Note:**Recursive solution is trivial, could you do it iteratively?

## 递归：

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
```

1. 首先需要一直对左子树迭代并将非空节点入栈
2. 节点指针为空后不再入栈
3. 当前节点为空时进行出栈操作，保存栈顶节点到result
4. 将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                result.append(root.val)
                root = root.right
        return result
```

## 复杂度分析 <a href="#fu-za-du-fen-xi" id="fu-za-du-fen-xi"></a>

最坏情况下栈保存所有节点，空间复杂度 $$O(n)$$, 时间复杂度 $$O(n)$$.