解题思路：

递归

迭代

代码：

Python

递归

1
2
3
4
5
6
7
8
9
10
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node: TreeNode, result: List[int]) -> None:
            if node == None: return
            dfs(node.left, result)
            result.append(node.val)
            dfs(node.right, result)
        result = []
        dfs(root, result)
        return result

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        cur = root
        while cur != None or stack:
            if cur != None:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result

C++

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }

    void dfs(TreeNode* node, vector<int> &tree_val) {
        if (node == NULL) return;
        dfs(node->left, tree_val);
        tree_val.push_back(node->val);
        dfs(node->right, tree_val);
    }
};

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()){
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;
            } else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};