题目

binary-tree-inorder-traversal

2. 算法

• 二叉树的遍历：左-根-右

* 递归

* 非递归：栈

* 非递归：morris traverl

3. 代码

* 递归

// Recursion

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> res;

        inorder(root, res);

        return res;

    }

    void inorder(TreeNode *root, vector<int> &res) {

        if (!root) return;

        if (root->left) inorder(root->left, res);

        res.push_back(root->val);

        if (root->right) inorder(root->right, res);

    }

};

* 非递归：stack

// Non-recursion

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> res;

        stack<TreeNode*> s;

        TreeNode *p = root;

        while (p || !s.empty()) {

            while (p) {

                s.push(p);

                p = p->left;

            }

            p = s.top();

            s.pop();

            res.push_back(p->val);

            p = p->right;

        }

        return res;

    }

};

* 非递归：mirror

// Non-recursion and no stack

class Solution {

public:

    vector<int> inorderTraversal(TreeNode *root) {

        vector<int> res;

        if (!root) return res;

        TreeNode *cur, *pre;

        cur = root;

        while (cur) {

            if (!cur->left) {

                res.push_back(cur->val);

                cur = cur->right;

            } else {

                pre = cur->left;

                while (pre->right && pre->right != cur) pre = pre->right;

                if (!pre->right) {

                    pre->right = cur;

                    cur = cur->left;

                } else {

                    pre->right = NULL;

                    res.push_back(cur->val);

                    cur = cur->right;

                }

            }

        }

        return res;

    }

};