二叉树后序遍历三种方法

二叉树后序遍历三种方法

一、递归写法

// 这个是偷懒不想多拆分函数
class Solution {
public:
    vector<int> tree;
    vector<int> postorderTraversal(TreeNode* root) {
        if(!root) return tree;
        if(root->left)
            postorderTraversal(root->left);
        if(root->right)
            postorderTraversal(root->right);
        tree.push_back(root->val);
        return tree;
    }
};
// 这也是一样的,但是时间复杂度更低,而且不需要另外的全局变量,比较好
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;
    stack<TreeNode*> toVisit;
    TreeNode* curNode = root;
    TreeNode* lastNode = NULL;
    while (curNode || !toVisit.empty()) {
        if (curNode) {
            toVisit.push(curNode);
            curNode = curNode -> left;
        }
        else {
            TreeNode* topNode = toVisit.top();
            if (topNode -> right && lastNode != topNode -> right)
                curNode = topNode -> right;
            else {
                nodes.push_back(topNode -> val);
                lastNode = topNode;
                toVisit.pop();
            }
        }
    }
    return nodes;
}

三、Morris 遍历

同样是搬运过来的。

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);
}
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> nodes;
    TreeNode* dump = new TreeNode(0);
    dump -> left = root;
    TreeNode* curNode = dump;
    while (curNode) {
        if (curNode -> left) {
            TreeNode* predecessor = curNode -> left;
            while (predecessor -> right && predecessor -> right != curNode)
                predecessor = predecessor -> right;
            if (!(predecessor -> right)) {
                predecessor -> right = curNode;
                curNode = curNode -> left;
            }
            else {
                reverseAddNodes(curNode -> left, predecessor, nodes);
                predecessor -> right = NULL;
                curNode = curNode -> right;
            }
        }
        else curNode = curNode -> right;
    }
    return nodes;
}

先序遍历
中序遍历

发表评论

电子邮件地址不会被公开。 必填项已用*标注