力扣-二叉树遍历

一、二叉树的递归遍历

关于递归要确定三件事情

• 递归函数的参数和返回值类型
  
• 递归的终止条件
  
• 递归的单层逻辑
  

二、二叉树的非递归遍历

递归本质上是使用栈去实现的，所以简朴的递归算法可以用栈去模拟实现。
以如下图片为例子，它的
前序遍历（中左右）是4 1 8 6 9；
后序遍历（左右中）是1 6 9 8 4；
中序遍历（左中右）是1 4 6 9 8。

2.1 二叉树的前序遍历和后序遍历

没那么困难，只要搞明确入栈、出栈操作代表着什么就行了。
2.1.1 二叉树的前序遍历

设存储结果的数组是 vector<int> result;

• 首先是根节点入栈，这是处置惩罚的出发点。(先访问的是根结点4，先处置惩罚的也是根结点4)
  
• 出栈：每次的出栈都是将栈顶的元素node弹出，送入到数组result中。这代表着要对此结点举行处置惩罚，对应地，会在栈中发生一些变化，对，就是入栈操作。
  
• 入栈：会将出栈结点node的两个孩子结点分别入栈，由于前序操作是”中左右“，栈是后进先出的，所以会让出栈结点node的右孩子先入栈、左孩子后入栈。
  

   为了更好地从前序遍历过渡到后序遍历，我想对前序遍历先有个直观的认识。
  

从根结点出发，然后是对根节点的孩子举行处置惩罚，在入栈的时候是先right后left的，出栈时候会先left，对左孩子举行处置惩罚，以及左孩子的孩子们。
由此可见，前序遍历的结果是由根开始，从上到下，先左后右的。我特别想提示自己的是，要处置惩罚完一个结点后，他就不属于二叉树了（不再需要等待被遍历），所以单层逻辑永远是一个”根“和它的孩子，它们三个关系是相当紧密的。
2.1.2 二叉树的后序遍历

   为什么是在前序遍历代码的基础上更改一下左右孩子入栈的顺序再多加一个数组翻转的操作，就可以实现二叉树的后序遍历？？
  我如今的想法是，后序遍历和前序遍历直观上来说都是从上到下的，只不外是左右的先后顺序差异，单层逻辑仍旧是一个”根“和它的孩子的处置惩罚方式，仍旧是相当紧密的关系。
2.2 二叉树的中序遍历

中序遍历是”左中右“，此时这个三角型结构（一个”根“和它的孩子）不是那么的稳固了，因为要先找到最左下角的结点，而非是先处置惩罚根节点了。所以二叉树的中序遍历要比上面讲的前序和后序遍历要麻烦一些。
中序遍历，先访问的是根结点4，先处置惩罚的却不是根结点4。
去模拟一下，看看是谁先入栈，又因为什么才能出栈。

先处置惩罚的一定是左下角的结点，所以由 根结点4 出发，会先将根结点的左孩子1入栈，如果1有左孩子要接着入栈，在这个过程中不对任何右孩子举行入栈操作。先处置惩罚的结点1先出栈进入数组result，但是结点1没有右孩子，所以不会再有操作。
根结点4的左子树齐备处置惩罚完了，然后处置惩罚结点4，并将结点4的右孩子8入栈，此时，我可以以为：结点8是新的”根结点“。

• 根结点入栈，但是通常不是先处置惩罚。
  
• 参加左孩子筹划：让根结点的左孩子，左孩子的左孩子，左孩子的左孩子的左孩子……入栈，直到左下角结点也入栈。
  
• 出栈处置惩罚：然后对栈顶的结点元素top举行弹出，写入到数组result中，将top的右孩子入栈，可以以为这个top的右孩子是新的“根结点”，继续举行参加左孩子筹划。
  
• 左孩子筹划完成后就举行出栈处置惩罚操作，也就是“参加左孩子筹划”和“出栈处置惩罚”是瓜代举行的。
  

三、代码

3.1 二叉树中序遍历-非递归方式

1. vector<int> inorderTraversal(TreeNode* root) {
2.         stack<TreeNode*> st;
3.         vector<int> result;
4.         if(root == nullptr) return result;
5.         // st.push(root);这里不能压入根结点
6.         TreeNode* cur = root;
7.         TreeNode* node = root;
8.         while(cur!= nullptr || !st.empty()){
9.             //加入左孩子计划
10.             if(cur != nullptr){
11.                 st.push(cur);
12.                 cout<<cur->val<<"入栈"<<endl;
13.                 cur = cur->left;
14.             } else{//出栈处理操作
15.                 node = st.top();
16.                 cout<<"加入数组中"<<node->val<<endl;
17.                 result.push_back(node->val);
18.                 st.pop();
19.                 cur = node->right;
20.             }
21.         }
22.             return result;
23.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。