内容摘要：刷Leetcode，需要知道一定的算法模板，本次先总结下二叉树的递归和非递归的遍历算法模板。二叉树的四种遍历方式，前中后加上层序遍历。对于二叉树的前中后层序遍历，每种遍历都可以递归和循环两种实现方法，

刷Leetcode，叉树需要知道一定的归和归算法模板，本次先总结下二叉树的非递递归和非递归的遍历算法模板。

二叉树的遍历四种遍历方式，前中后加上层序遍历。算法对于二叉树的模板前中后层序遍历，每种遍历都可以递归和循环两种实现方法，叉树且每种遍历的归和归递归实现都比循环实现要简洁。下面做一个小结，非递看了《代码随想录》哈工大大佬的遍历刷题指南，深受启发，算法因，模板下面代码有一定来源《代码随想录》。叉树

递归

下面伪代码是归和归二叉树遍历的递归算法模板，顺序是非递中左右，也就是前序遍历，改变中左右三行代码的顺序，前中后序三种递归遍历轻松解决。

def preorderTraversal(root: TreeNode) -> List[int]:     res = []     def help(root):         if not root: return         res.append(root.val) # 中         help(root.left) # 左         help(root.right) # 右     help(root)     return res 

对此也提供C++代码，递归算法模板一定要加上终止条件，不然一入递归深似海，从此offer是源码库路人，来源代码随想录。

void help(TreeNode * root , vector<int> &res) {      if (root == nullptr) {          return;     }     res.push_back(root->val); // 中     help(root->left,res); // 左     help(root->right,res); //右 } vector<int> preorderTraversal(TreeNode* root) {      vector<int> res;     help(root,res);     return res; } 

迭代

迭代遍历二叉树的比递归难度加大，其实使用了一个栈的数据结构，《代码随想录》非常巧妙的使用空指针来作标记，原理是将处理的节点放入栈之后，紧接着放入一个空指针作为标记。

由于栈是先进后出，所以前序遍历的顺序中左右，在加到栈中，需要反过来进行添加，每添加一个元素在后面添加一个空指针，在Python中也可以使用None来代替。

下面是具体的伪代码，至于中序和后序遍历，改下向栈中添加节点的顺序即可。

def preorderTraversal(root: TreeNode) -> List[int]:       result = []       st= []       # 1、判断root       if root:           st.append(root)       while st:           node = st.pop()           if node != None:               # 右左中 添加到栈中，然后中左右拿出               if node.right: #右                   st.append(node.right)               if node.left: #左                   st.append(node.left)               st.append(node) #中               # 添加一个空指针 记录节点               st.append(None)           else:               # node是空指针，那么下一个就是加入的节点               node = st.pop()               result.append(node.val)       return result 

下面是云服务器具体的C++代码，由于C++中的stack中pop之后，没有返回值，因此需要额外注意。

vector<int> preorderTraversal(TreeNode* root) {          vector<int>res;         stack<TreeNode*> st;         if (root != nullptr) st.push(root);         while(!st.empty()){              TreeNode* node = st.top();             if(node != nullptr){                  st.pop();                 if(node->right) st.push(node->right);                 if (node->left) st.push(node->left);                 st.push(node);                 st.push(NULL);             }else{                  // 需要额外注意下                 st.pop();                 node = st.top();                 st.pop();                 res.push_back(node->val);             }         }         return res;     } 

层次遍历

其实，树的遍历也分为两种，分别是深度优先遍历和广度优先遍历。关于树的不同深度优先遍历(前序，中序和后序遍历)就是递归和非递归的写法。广度优先遍历在树中，就是层次遍历。

在二叉树的层级遍历中，我们需要用到队列这个数据结构，帮助我们完成遍历。

在Python伪代码中，

def levelOrder(root: TreeNode) -> List[List[int]]:  # 1、判断root    if not root:         return []     # 把root添加到quene 中     quene = [root]     out_list = []     while quene:      # while 第一步就是求length          length = len(queue)           in_list = []         for _ in range(length):          # 在C++中，这里需要两行             curnode = queue.pop(0)  # （默认移除列表最后一个元素）这里需要移除队列最头上的那个             in_list.append(curnode.val)             if curnode.left: queue.append(curnode.left)             if curnode.right: queue.append(curnode.right)         out_list.append(in_list)     return out_list 

通过上面的Python伪代码，进行书写更高效的C++代码。

class Solution {  public:     vector<vector<int>> levelOrder(TreeNode* root) {          vector<vector<int>> res;         queue<TreeNode*> que;         // 判断  root         if (root != nullptr) que.push(root);         while(!que.empty()) {               // 开始先求队列的站群服务器长度             int size = que.size();             vector<int> vec;             // 迭代添加节点元素             for (int i = 0 ; i<size; i++){                  TreeNode* node = que.front();                 que.pop();                 vec.push_back(node->val);                 if (node->left) que.push(node->left);                 if (node->right) que.push(node->right);             }             res.push_back(vec);         }         return res;     } }; 

上述为树的遍历模板。其实本质上也是深度优先遍历与广度优先遍历的算法模板，许多其它操作都是建立在树遍历操作的基础之上，因此掌握树的所有遍历方法，等于解决了一半树的题目。