# Binary Tree Inorder Traversal

Iterative

在进入while循环之前什么都不做，先把cur=root。进去之后，首先再用一个while一直往左走直到尽头，也一路的存入stack，然后把顶元素存入result，并且这时候把cur变成顶元素的右儿子。

想象cur从root初始开始打怪兽。stack为空不加入root。在while里cur一路给stack充值直到cur空，然后stack pop给cur值，然后cur到right 继续。

注意此处while条件是or

Python

```python
from typing import (
    List,
)
from lintcode import (
    TreeNode,
)

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A Tree
    @return: Inorder in ArrayList which contains node values.
    """
    def inorder_traversal(self, root: TreeNode) -> List[int]:
        # write your code here
        res = []
        stack = []
        cur = root
        #一个while判断cur和stack即可
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
        
            cur = stack.pop()
            #List函数没有add
            res.append(cur.val)
            #只移动指针，不需要塞入栈,因为中序的话root已经遍历了，右树可以直接遍历无需栈。
            cur = cur.right
        #记得返回结果
        return res   

```

```

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if(root == null)
            return ret;
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur = root;

        while(cur != null || !s.isEmpty()){
            while(cur != null){
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            ret.add(cur.val);
            cur = cur.right;
        }

        return ret;
    }
```

Recursive

```
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        if(root == null)
            return ret;
        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);
        ret.addAll(left);
        ret.add(root.val);
        ret.addAll(right);
        return ret;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l3er-cha-shu-he-fen-zhi-fa/binary-tree-inorder-traversal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.