LeetCode题66~68： 二叉树的遍历

本文主要是介绍LeetCode题66~68： 二叉树的遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述：

给出一棵二叉树，返回其节点值的前序遍历、中序遍历、后序遍历。
例如：
4
/ \
2 6
/ \ / \
1 3 5 7
前序遍历（根—左—右）：4， 2， 1， 3， 6， 5， 7
中序遍历（左—根—右）：1， 2， 3， 4， 5， 6， 7
后序遍历（左—右—根）：1， 3， 2， 5， 7， 6， 4

2. 二叉树的数据结构：

struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int v = 0, TreeNode *l = NULL, TreeNode *r = NULL):val(v),left(l),right(r){}
};

3. 前序遍历

3.1 递归

vector<int> result;//存放遍历结果vector<int> preorder1(TreeNode *root) {           if(root){result.push_back(root->val);preorder1(root->left);preorder1(root->right);}return result;}

3.2 非递归（栈）

首先把根节点入栈，然后在每次循环中执行以下操作：
• 此时栈顶元素即为当前的根节点，弹出并打印当前的根节点。
• 把当前根节点的右儿子和左儿子分别入栈（注意是右儿子先入栈左儿子后入栈，这样的话下次出栈的元素才是左儿子，这样才符合前序遍历的顺序要求：根节点->左儿子->右儿子）。

vector<int> preorder2(TreeNode *root) {vector<int> result;//存放遍历结果stack<TreeNode *> stk;if(root){stk.push(root);while(!stk.empty()){TreeNode *p = stk.top();stk.pop();result.push_back(p->val);if(p->right != NULL){stk.push(p->right);}if(p->left != NULL){stk.push(p->left);}}}return result;}

3.3 非递归（线索化-Morris遍历）

步骤：
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。输出当前节点（在这里输出，这是与中序遍历唯一一点不同）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。

vector<int> preorder3(TreeNode *root){vector<int> result;//存放遍历结果TreeNode* pCur = root;  TreeNode* pre;//用于找到当前结点中序遍历的直接前驱  while(pCur)  { if(pCur->left == NULL)//case 1  {result.push_back(pCur->val); pCur = pCur->right; }else  {  //找当前结点在中序遍历中的前驱结点pre = pCur->left; while(pre->right != NULL && pre->right != pCur)  {pre = pre->right;  }if(pre->right == NULL)//case 2a:构成线索二叉树  {  pre->right = pCur;  result.push_back(pCur->val);  pCur = pCur->left;  }  else//case 2b:当前结点左子树遍历完成，断开线索  {  pre->right = NULL;  pCur = pCur->right;  }  }  }return result;}

4. 中序遍历

4.1 递归

    vector<int> result;  //存放遍历结果vector<int> inorder1(TreeNode *root){if(root){inorder1(root->left);result.push_back(root->val);inorder1(root->right);}return result;}

4.2 非递归（栈）

中序遍历实现原理：对于任一节点P，
1. 若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点，然后再对当前节点进行相同的处理；
2. 若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点，看其是否为空；
a) 若不为空，则重复1）和2）的操作；
b) 若为空，则执行出栈操作，输出栈顶节点，并将出栈的节点的右孩子置为当前节点，看其是否为空，重复以上的操作；
3. 直到当前节点P为NULL并且栈为空，则遍历结束。

vector<int> inorder2(TreeNode *root){vector<int> result;  //存放遍历结果TreeNode  *pCur = root;  stack<TreeNode*> stk;  while(pCur != NULL || !stk.empty())  { if(pCur->left == NULL){result.push_back(pCur->val);  pCur = pCur->right;  }  else  {  stk.push(pCur);  pCur = pCur->left;  }  //如果当前结点pCur为NULL且栈不空，则将栈顶结点出栈，  //同时置其右孩子为当前结点，循环判断，直至pCur不为空  while(!pCur && !stk.empty())  {  pCur = stk.top();  stk.pop();  result.push_back(pCur->val);  pCur = pCur->right;  }  }  return result;}

4.3 非递归（线索化-Morris遍历）

步骤：
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
3. 重复以上1、2直到当前节点为空。

vector<int> inorder3(TreeNode *root){vector<int> result;  //存放遍历结果TreeNode *pCur = root;  TreeNode *pre = NULL; //用于找到当前结点的直接前驱结点while(pCur != NULL){if(pCur->left == NULL)  //case 1{result.push_back(pCur->val);pCur = pCur->right;}else{//找当前结点在中序遍历中的前驱结点pre = pCur->left;while(pre->right != NULL && pre->right != pCur){pre = pre->right;}if(pre->right == NULL)  //case 2.a{pre->right = pCur;pCur = pCur->left;}else                     //case 2.b{pre->right = NULL;result.push_back(pCur->val);pCur = pCur->right;}}}return result;}

5. 后序遍历

5.1 递归

vector<int> result;  //存放遍历结果vector<int> postorder1(TreeNode *root){if(root){postorder1(root->left);postorder1(root->right);result.push_back(root->val);}return result;}

5.2 非递归（栈）

因为后序遍历的顺序是：左子树->右子树->根节点，于是我们在前序遍历的代码中，当访问完当前节点后，先把当前节点的左子树入栈，再把右子树入栈，这样最终得到的顺序为：根节点->右子树->左子树，刚好是后序遍历倒过来的版本，于是把这个结果做一次翻转即为真正的后序遍历。而翻转可以通过使用另外一个栈简单完成，这样的代价是需要两个栈，但就复杂度而言，空间复杂度仍然是O(h)。

vector<int> postorder2(TreeNode *root){vector<int> result;  //存放遍历结果stack<TreeNode *> stk1, stk2;if(root){stk1.push(root);}while(!stk1.empty()){TreeNode *pCur = stk1.top();stk1.pop();stk2.push(pCur);if(pCur->left != NULL){stk1.push(pCur->left);}if(pCur->right != NULL){stk1.push(pCur->right);}}while(!stk2.empty()){result.push_back(stk2.top()->val);stk2.pop();}return result;}

5.3 非递归（线索化-Morris遍历）

后续遍历稍显复杂，需要建立一个临时节点temp，令其左孩子是root，并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
步骤：
首先新创建一个临时结点temp，并令其左孩子指向根节点，右孩子指向NULL。
1）如果当前节点的左孩子为空，则将其右孩子作为当前节点。
2）如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
3）重复以上1、2直到当前节点为空。

void reverse(TreeNode* from, TreeNode* to)  //将from到to的结点的右孩子指针逆转  {                                            if(from == to)  return; TreeNode *x = from, *y = from->right, *z;  while(x != to)  {  z = y->right;  y->right = x;  x = y;  y = z;              }  } void printReverse(TreeNode* from, TreeNode* to, vector<int> &ret)  {  reverse(from, to);  TreeNode *p = to;  while(1)  {  ret.push_back(p->val);  if(p == from)  break;  p = p->right;  }  reverse(to, from);  } vector<int> postorder3(TreeNode *root){vector<int> result;//存放遍历结果 TreeNode *temp = new TreeNode(0);temp->left = root;TreeNode* pCur = temp;TreeNode* pre = NULL;//用于找到当前结点中序遍历的直接前驱  while(pCur != NULL){if(pCur->left == NULL){pCur = pCur->right;}else{//找当前结点在中序遍历中的前驱结点pre = pCur->left;while(pre->right != NULL && pre->right != pCur){pre = pre->right;}if(pre->right == NULL)  //case: 2.a{pre->right = pCur;pCur = pCur->left;}else                    //case: 2.b{printReverse(pCur->left, pre, result);pre->right = NULL;pCur = pCur->right;}}}//删除辅助结点temp->left = NULL;delete(temp);temp = NULL;return result;}

ps: 完整测试代码见我的代码片：https://code.csdn.net/snippets/1760021

参考博客：
1、二叉树遍历（递归、非递归、Morris遍历）
2、二叉树前序、中序和后序的遍历方法（递归、用栈和使用线索化）
3、Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）

Note: 以上三篇博客对我写作本文起了很大作用，在此非常感谢三位博主。

这篇关于LeetCode题66~68： 二叉树的遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---