Binary Tree Inorder Traversal Problem


Description

LeetCode Problem 94.

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

1
2
Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

Example 4:

1
2
Input: root = [1,2]
Output: [2,1]

Example 5:

1
2
Input: root = [1,null,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100


Sample C++ Code

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

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




Related Posts

Maximum Binary Tree II Problem

LeetCode 998. A maximum tree is a tree where every...

Construct Binary Tree from Preorder and Inorder Traversal Problem

LeetCode 105. Given two integer arrays preorder and inorder where...

Binary Tree Inorder Traversal Problem

LeetCode 94. Given an m x n grid of characters...