[LeetCode] Binary Tree Traversal Collection

我们来看一下二叉树的结构,下面这是他的节点

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

前序遍历


vector<int> preorderTraversal(TreeNode *root) {
    vector<int> v;
    if (!root) return v;
    stack<TreeNode *> stk;
    TreeNode *cur = root;
    while (cur || !stk.empty()) {
        if (cur) {
            v.push_back(cur->val);
            stk.push(cur);
            cur = cur->left;
        }
        else {
            // finish visited left child tree
            cur = stk.top(); stk.pop(); // trace back to parent node
            cur = cur->right;
        }
    }
    return v;
}

中序遍历


vector<int> inorderTraversal(TreeNode *root) {
    vector<int> ans;
    stack<TreeNode *> stk;
    TreeNode *node = root;
    while (node || !stk.empty()) {
        while (node) {
            stk.push(node);
            node = node->left;
        }
        if (!stk.empty()) {
            node = stk.top();
            ans.push_back(node->val);
            stk.pop();
            node = node->right;
        }
    }
    return ans;
}

后序遍历解法-1


vector<int> postorderTraversal(TreeNode *root) {
    unordered_map<TreeNode *, bool> m; // mark the node if visited first time
    stack<TreeNode *> s;
    vector<int> ans;
    while (!s.empty() || root) {
        while (root) {
            s.push(root);
            m[root] = true;
            root = root->left;
        }
        if (!s.empty()) {
            TreeNode *curr = s.top();
            s.pop();
            if (m[curr]) {
                s.push(curr);
                root = curr->right;
                m[curr] = false;
            }
            else {
                ans.push_back(curr->val);

            }
        }
    }
    return ans;
}

后序遍历解法-2


vector<int> postorderTraversal(TreeNode *root) {
    vector<int> ans;
    if (!root) return ans;
    stack<TreeNode *> s;
    s.push(root);

    TreeNode *curr, *prev = NULL;
    while (!s.empty()) {
        curr = s.top();
        // visit the none-children node or visit node with its children visted
        if (!curr->left && !curr->right ||
            prev && (prev==curr->left || prev==curr->right)) {
            ans.push_back(curr->val);
            s.pop();
            prev = curr;
        }
        else {
            if (curr->right) s.push(curr->right);
            if (curr->left) s.push(curr->left);
        }
    }
    return ans;
}

层级遍历


vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int> > ans;
    if (!root) return ans;
    vector<int> level;
    queue<TreeNode *> que;
    que.push(root);
    while (!que.empty()) {
        que.push(NULL);
        level.clear();
        while (que.front()) {
            TreeNode *tmp = que.front();
            que.pop();
            level.push_back(tmp->val);
            if (tmp->left) que.push(tmp->left);
            if (tmp->right) que.push(tmp->right);
        }
        que.pop();
        ans.push_back(level);
    }
    return ans;
}