qiaoxu123
1/4/2019 - 12:57 AM

94. Binary Tree Inorder Traversal

二叉树的中序遍历 经过查找，遍历存在着三种方法，在这汇总整理下。

  • Recursive solution : O(n) time and O(n) space

  • Iterative solution using stack : O(n) time and O(n) space

  • Morris traversal : O(n) time and O(1) space

可参考这篇博客

recursive.cpp
content_copyfile_download
//Runtime: 0 ms, faster than 100.00%

#include <ios>
static auto fastInput = []() {
    ios_base::sync_with_stdio(false),cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    vector<int> array;
    
    vector<int> inorderTraversal(TreeNode* root) {
        travelTree(root);
        return array;
    }
    
    void travelTree(TreeNode* root){
        if(root){
            travelTree(root->left);
            array.push_back(root->val);
            travelTree(root->right);
        }
    }
};
iterative.cpp
content_copyfile_download
//Runtime: 0 ms, faster than 100.00%

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> nodes;
        stack<TreeNode*> todo;
        TreeNode* cur = root;
        while(cur || !todo.empty()){
            if(cur){
                todo.push(cur);
                cur = cur->left;
            }
            else{
                cur = todo.top();
                todo.pop();
                nodes.push_back(cur->val);
                cur = cur->right;
            }
        }
        return nodes;
    }
};
morris.cpp
content_copyfile_download
//Runtime: 0 ms, faster than 100.00%

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> nodes;
        while(cur){
            if(cur->left){
                TreeNode* 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;
                    nodes.push_back(cur->val);
                    cur = cur->right;
                }
            }
            else{
                nodes.push_back(cur->val);
                cur = cur->right;
            }
        }
        return nodes;
    }
};