2020-11-20

史上最全遍历二叉树详解（C++模板）

根据leetcode的题目去学习二叉树遍历的知识点

史上最全遍历二叉树详解（C++模板）

二叉树的初始化

首先要构造一个二叉树，这个能够方便我们对其了解。众所周知，二叉树遍历方式用前序遍历，中序遍历，后序遍历和层次遍历；每种遍历的方法还有不相同，前中后序遍历可以用迭代和递归完成，而层次遍历更多选择bfs（广度优先这种方法）作为一名学生，更加应该去掌握利用迭代方法

上代码

struct TreeNode{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int val1,TreeNode *l = nullptr,TreeNode *r = nullptr){//构造函数
    val = val1;
    left = l;
    right = r;
  }
};
初始化
void CreateTreeNode(TreeNode* &root){ //表示操作实参变量 
	int s;
	cin >> s;
	if(s != 0){  //如果输入为0，则认为无左子树或者右子树 
		root = new TreeNode();
		root->val = s; 
		CreateTreeNode(root->left);//构建左子树 
		CreateTreeNode(root->right); //构建右子树 
	}else{
		root = NULL;
		return ; 
	}
}

一、利用递归遍历二叉树

因为是递归遍历，就不要过多的文字说明，这是因为比较常规，我尽量都会直接给出代码，而不会过度去说明。

1.1前序遍历（根节点-左子树-右子树）

定义preorder(root)表示当前遍历到root节点的答案。按照定义，我们只要首先将root节点的值加入答案，然后递归调用preorder(root.left)来遍历root节点的左子树，最后递归调用preorder(root.right)来遍历root节点的右子树即可，递归终止的条件为碰到空节点。

void preorder(TreeNode *root, vector<int> &res) {
     if (root == nullptr) {
         return;
     }
     res.push_back(root->val);   //*注意看这下面三行（然后你就会发现一些规律）
     preorder(root->left, res);
     preorder(root->right, res);
 }
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     preorder(root, res);
       return res;
 }

1.2中序遍历（左子树-根节点-右子树）

定义inorder(root) 表示当前遍历到root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历root节点的左子树，然后将root节点的值加入答案，再递归调用inorder(root.right) 来遍历root 节点的右子树即可，递归终止的条件为碰到空节点

void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);//这行跟之前有些不同
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
}

1.3 后序（左子树-右子树-根节点）

定义postorder(root)表示当前遍历到root节点的答案。按照定义，我们只要递归调用postorder(root->left)来遍历root节点的左子树，然后递归调用postorder(root->right)来遍历 root节点的右子树，最后将root节点的值加入答案即可，递归终止的条件为碰到空节点。

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

1.4遍历的模板如下

void 函数名(TreeNode *root, vector<int> &res) {
    if (root == nullptr) {
        return;
    }
    #后序遍历
    函数名(root->left, res);
    函数名(root->right, res);
    res.push_back(root->val);
    #中序遍历
    函数名(root->left, res);
    res.push_back(root->val);
    函数名(root->right, res);
    #前序遍历
    res.push_back(root->val);
    函数名(root->left, res);
    函数名(root->right, res);
}
vector<int> postorderTraversal(TreeNode *root) {
    vector<int> res;
    函数名(root, res);
    return res;
}

二、利用迭代遍历

2.1前序

迭代算法，我看了那么多博主的文章，基本都是用栈，一方面也是比较好理解，另外一方面也比较好模板化。代码是重复性的，有规律的。只有认真去理解，才会便于自己去写代码和规范自己代码。

递归思路：先树根，然后左子树，然后右子树。每棵子树递归。在迭代算法中，思路演变成，每到一个节点 A，就应该立即访问它。因为，每棵子树都先访问其根节点。对节点的左右子树来说，也一定是先访问根。
栈S;

while(root|| S不空){
    while(root){
        将root节点的值放入res；
        root压入S;
        root = root=root->left;
    }
    root = 栈顶
    s.pop();
    root = root->right;
}

完整代码如下

vector<int> preorderTraversal(TreeNode* root) {
     vector<int> res;
     if (root == nullptr) {
         return res;
     }
     stack<TreeNode*> stk;
     while (!stk.empty() || root != nullptr) {
         while (root != nullptr) {     //这一步是将root->left全部压入栈
             res.push_back(root->val);  //这个可以用emplace_back函数替代
             stk.push(root);
             root = root->left;
         }
         root = stk.top();
         stk.pop();
         root = root->right;
     }
     return res;
 }

2.2中序

已知前序怎么去操作，那么对于中序来说那就变得更加简单；只是一个读取的顺序不一样而已。中前后到前中后，无非就是选择读取左结点和头节点的顺序。

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);//跟前序的时候，就是讨论何时把结点放到数组中去
            root = root->right;
        }
        return res;
    }

2.3后序

后序主要跟中序的区别就是：头结点比较晚读取，那就要去思考，跟之前的方法是不是差不多，其中不同点在于那里。
难点判断是不是有右子树，如果有的话，我们就要把那个头结点压进入栈，然后在压入右节点。这样根绝栈的特性，我们就可以知道，先出来就是右结点然后就是做节点咯

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> res;
    if (root == nullptr) {
        return res;
    }
    stack<TreeNode *> stk;
    TreeNode *prev = nullptr;  //这个主要是来判断是否弹出过左结点
    while (root != nullptr || !stk.empty()) {
        while (root != nullptr) {
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if (root->right == nullptr || root->right == prev) {
            res.push_back(root->val);// root->right == prev是为了压入头结点
            prev = root;
            root = nullptr;  // 为了防止重复压入左节点
        } else {
            stk.push(root);
            root = root->right;
        }
    }
    return res;
}

后序的迭代相对来说比较难一点，网上还有另外一种解法（可以自行去了解，那种比较简单，利用了对称的原则）

2.4迭代模板

前序和中序:
vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                // res.push_back(root->val); 放在着就是前序
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            //  res.push_back(root->val); 放在着就是中序
            root = root->right;
        }
        return res;
    }

后序的模板基本就是靠理解咯

三、层次遍历

层次遍历采取的是bfs，这种比较常见，当然你也可以采取dfs，这种当然可以。我主要去介绍bfs，dfs这种稍微比较不常见。

vector<vector<int>> levelOrder(TreeNode* root) {
    vector <vector <int>> ret;
    if (!root) {
        return ret;
    }

    queue <TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = q.size();  //这个很重要，如果没有这个，程序运行后会得到错误的结果
        ret.push_back(vector <int> ());
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front(); q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    } 
    return ret;
}

本文参考：

-二叉树的前序遍历
-二叉树的中序遍历
-二叉树的后序遍历
-二叉树的层序遍历