二叉树遍历高级版

84 阅读 0 评论 56 点赞

我是靠谱客的博主英勇帆布鞋，最近开发中收集的这篇文章主要介绍二叉树遍历高级版，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前序遍历:

（1）递归思路：先树根，然后左子树，最后右子树。

void preorderTraversal(TreeNode* current, vector<int> &temp_result) {
    if (current == NULL) return;
    temp_result.push_back(current->val);
    if (current->left) helper1(current->left, temp_result);
    if (current->right) helper1(current->right, temp_result);
    return;
}

（2）迭代思路：对节点的左右子树来说，一定会先访问根，然后遍历完左子树后，再遍历右子树。因此，在访问完根节点后，遍历左子树前，要将右子树压入栈。

void preorderTraversal(TreeNode* current, vector<int> &temp_result) {
    std::stack<TreeNode*> tree_stack;
    while(tree_stack.size() || current != NULL) {
        while(current != NULL) {
            temp_result.push_back(current->val);
            tree_stack.push(current->right);
            current = current->left;
        }
        current = tree_stack.top();
        tree_stack.pop();
    }
    return;
}

中序遍历:

（1）递归思路：先左子树，然后树根，最后右子树。

void inorderTraversal(TreeNode* root, vector<int> &temp_result) {
    if (root == NULL) return;
    if (root->left) helper1(root->left, temp_result);
    temp_result.push_back(root->val);
    if (root->right) helper1(root->right,temp_result);
}

（2）迭代思路：对节点的左右子树来说，一定会先访问根，因为根的访问在中间，将根先入栈。然后遍历左子树，接着访问根，最后遍历右子树。在访问完根后，根就可以出栈了。因为根和其左子树都已经访问完成。

void inorderTraversal(TreeNode* currrnt, vector<int> &temp_result) {
    std::stack<TreeNode*> tree_stack;
    while(tree_stack.size() || currrnt != NULL) {
        while(currrnt != NULL) {
            tree_stack.push(currrnt);
            currrnt = currrnt->left;
        }
        currrnt = tree_stack.top();
        temp_result.push_back(currrnt->val);
        tree_stack.pop();
        currrnt = currrnt -> right;
    }
    return;
}

后序遍历:

（1）递归思路：先左子树，然后右子树，最后树根。

void postorderTraversal(TreeNode* current, vector<int> &temp_result) {
    if (current == NULL) return;
    if (current -> left) helper1(current->left, temp_result);
    if (current -> right) helper1(current->right, temp_result);
    temp_result.push_back(current->val);
    return;
}

（2）迭代思路：

1.按照根右左处理，然后逆序：

对节点的左右子树来说，一定会先访问根，然后遍历完右子树后，再遍历左子树。因此，在访问完根节点后，遍历右子树前，要将左子树压入栈。如此得到遍历结果是按照根右左的顺序，与后续的左右根刚好相反，因此最后对遍历的结果进行逆向即可；

void postorderTraversal(TreeNode* current, vector<int> &temp_result) {
    std::stack<TreeNode*> tree_stack;
    while(tree_stack.size() || current != NULL) {
        while(current != NULL) {
            temp_result.push_back(current->val);
            tree_stack.push(current->left);
            current = current->right;
        }
        current = tree_stack.top();
        tree_stack.pop();
    }
    std::reverse(temp_result.begin(), temp_result.end());
    return;
}

2.按照左右根处理：

对节点的左右子树来说，一定会先访问根，然后遍历左子树后，后续遍历的难点在于判断是从left还是right返回的根节点，需要借助一个pre_node记录right节点是否被访问过，只有当right节点为空和右侧节点已经被访问过的时候才将根节点的数据写入vector中返回；

void postorderTraversal(TreeNode* current, vector<int> &temp_result) {
    std::stack<TreeNode*> tree_stack;
    TreeNode* pre_node = NULL;
    while(tree_stack.size() || current != NULL) {
        while(current != NULL) {
            tree_stack.push(current);
            current = current->left;
        }
        current = tree_stack.top();
        if (NULL == current->right || pre_node == current->right) {
            temp_result.push_back(current->val);
            tree_stack.pop();
            pre_node = current;
            current = NULL;
        } else {
            current = current->right;
            pre_node = NULL;
        }
    }
    return;
}