Description

Binary Tree Inorder Traversal

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> r;
        inorderVisit(r, root);
        return r;
    }

private:
    void inorderVisit(vector<int> &r, TreeNode *node) {
        std::stack<TreeNode *> s;
        auto *cur = node;
        while(cur || !s.empty()) {
            while(cur) {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            r.push_back(cur->val);
            cur = cur->right;
        }
    }

    /* 递归
    void inorderVisit(vector<int> &r, TreeNode *node) {
        if (!node) {
            return;
        }
        if (node->left) {
            inorderVisit(r, node->left);
        }
        r.push_back(node->val);
        if (node->right) {
            inorderVisit(r, node->right);
        }
    }
    */
};