二叉树遍历

vector<int> inorderTraversal(TreeNode *root) {
    // using stack
    vector<int> nodes;
    stack<TreeNode *> todoStack;
    while (root || !todoStack.empty()) {
        while (root) {
            todoStack.push(root);
            root = root->left;
        }
        root = todoStack.top();
        todoStack.pop();
        nodes.push_back(root->val);
        root = root->right;
    }
    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);
    }
    vector<int> inorderTraversal(TreeNode *root) {
        // recursive
        vector<int> nodes;
        inorder(root, nodes);
        return nodes;
    }

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

class Solution {
   public:
    vector<int> inorderTraversal(TreeNode *root) {
        // morris traversal
        vector<int> nodes;
        while (root) {
            if (root->left) {
                TreeNode *pre = root->left;
                while (pre->right && pre->right != root) {
                    pre = pre->right;
                }
                if (!pre->right) {
                    pre->right = root;
                    root = root->left;
                } else {
                    pre->right = NULL;
                    nodes.push_back(root->val);
                    root = root->right;
                }
            } else {
                nodes.push_back(root->val);
                root = root->right;
            }
        }
        return nodes;
    }
};

vector<int> preorderTraversal(TreeNode *root) {
        // Iterative solution using stack
        vector<int> nodes;
        stack<TreeNode *> todo;
        while (root || !todo.empty()) {
            if (root) {
                nodes.push_back(root->val);
                if (root->right) {
                    todo.push(root->right);
                }
                root = root->left;
            } else {
                root = todo.top();
                todo.pop();
            }
        }
        return nodes;
    }

   void preorder(TreeNode *root, vector<int> &nodes) {
        if (!root) {
            return;
        }
        nodes.push_back(root->val);
        preorder(root->left, nodes);
        preorder(root->right, nodes);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        // Recursive solution
        vector<int> nodes;
        preorder(root, nodes);
        return nodes;
    }

vector<int> preorderTraversal(TreeNode *root) {
        vector<int> nodes;
        while (root) {
            if (root->left) {
                TreeNode *pre = root->left;
                while (pre->right && pre->right != root) {
                    pre = pre->right;
                }
                if (!pre->right) {
                    pre->right = root;
                    nodes.push_back(root->val);
                    root = root->left;
                } else {
                    pre->right = NULL;
                    root = root->right;
                }
            } else {
                nodes.push_back(root->val);
                root = root->right;
            }
        }
        return nodes;
    }

 vector<int> postorderTraversal(TreeNode *root) {
        // Iterative solution using stack
        vector<int> nodes;
        stack<TreeNode *> todo;
        TreeNode *last = NULL;
        while (root || !todo.empty()) {
            if (root) {
                todo.push(root);
                root = root->left;
            } else {
                TreeNode *node = todo.top();
                if (node->right && last != node->right) {
                    root = node->right;
                } else {
                    nodes.push_back(node->val);
                    last = node;
                    todo.pop();
                }
            }
        }
        return nodes;
    }

    void postorder(TreeNode* root, vector<int>& nodes) {
        if (!root) {
            return;
        }
        postorder(root -> left, nodes);
        postorder(root -> right, nodes);
        nodes.push_back(root -> val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        postorder(root, nodes);
        return nodes;
    }

 vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nodes;
        TreeNode* dummy = new TreeNode(0);
        dummy -> left = root;
        TreeNode* cur = dummy;
        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 {
                    reverseAddNodes(cur -> left, pre, nodes);
                    pre -> right = NULL;
                    cur = cur -> right;
                }
            } else {
                cur = cur -> right;
            }
        }
        return nodes;
    }
private:
    void reverseNodes(TreeNode* start, TreeNode* end) {
        if (start == end) {
            return;
        }
        TreeNode* x = start;
        TreeNode* y = start -> right;
        TreeNode* z;
        while (x != end) {
            z = y -> right;
            y -> right = x;
            x = y;
            y = z;
        }
    }
    void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
        reverseNodes(start, end);
        TreeNode* node = end;
        while (true) {
            nodes.push_back(node -> val);
            if (node == start) {
                break;
            }
            node = node -> right;
        }
        reverseNodes(end, start);
    }