代码随想录算法训练营第十四天| 理论基础 递归遍历 迭代遍历

理论基础 

     卡哥建议：需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义 

    文章讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

     补充的知识点：

     名词的概念看卡哥文章。二叉树分为，满二叉树和完全二叉树，

    完全二叉树的底部一定是从左到右连续的。这两种树都没有数值的，

    而二叉搜索树，平衡二叉搜索树是有数值的。

    平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

    二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。二叉树节点的深度先不写了，后面做题会碰到。下面的图片可以放大看。

    二叉树主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
2. 广度优先遍历：一层一层的去遍历。

    那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

• 深度优先遍历
  • 前序遍历（递归法，迭代法），中左右（中间节点的顺序就是所谓的遍历方式）
  • 中序遍历（递归法，迭代法），左中右
  • 后序遍历（递归法，迭代法），左右中
• 广度优先遍历
  • 层次遍历（迭代法）

递归遍历 （必须掌握）

     卡哥建议：二叉树的三种递归遍历掌握其规律后，其实很简单 

    题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html

     补充（详细的见卡哥文章）：

      递归三部曲：    

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

     前序遍历（递归法）代码：

 1 void traversal(TreeNode* cur, vector<int>& vec) {
 2         if (cur == NULL) return;
 3         vec.push_back(cur->val);    // 中
 4         traversal(cur->left, vec);  // 左
 5         traversal(cur->right, vec); // 右
 6     }
 7     vector<int> preorderTraversal(TreeNode* root) {
 8         vector<int> result;
 9         traversal(root, result);
10         return result;
11     }

      中序遍历（递归法）代码：

1 void traversal(TreeNode* cur, vector<int>& vec) {
2     if (cur == NULL) return;
3     traversal(cur->left, vec);  // 左
4     vec.push_back(cur->val);    // 中
5     traversal(cur->right, vec); // 右
6 }

      后序遍历（递归法）代码：

1 void traversal(TreeNode* cur, vector<int>& vec) {
2     if (cur == NULL) return;
3     traversal(cur->left, vec);  // 左
4     traversal(cur->right, vec); // 右
5     vec.push_back(cur->val);    // 中
6 }

迭代遍历 （基础不好的录友，迭代法可以放过）

      题目链接/文章讲解/视频讲解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html

     前序遍历（迭代法）代码：

 1  vector<int> preorderTraversal(TreeNode* root) {
 2         stack<TreeNode*> st;
 3         vector<int> result;
 4         if (root == NULL) return result;
 5         st.push(root); //先把根节点入栈
 6         while (!st.empty()) {
 7             TreeNode* node = st.top();                       //指针先从根节点开始遍历， 中
 8             st.pop();
 9             result.push_back(node->val);
10             if (node->right) st.push(node->right);           // 右（空节点不入栈）
11             if (node->left) st.push(node->left);             // 左（空节点不入栈）
12         }
13         return result;
14     }

     后序遍历（迭代法）代码：

    前序遍历是中左右，后序遍历是左右中。前序遍历在代码里写的是中右左，然后翻转，变成左右中。注意的是在后序遍历的代码里是要先改成中左右，再翻转。

 1 vector<int> postorderTraversal(TreeNode* root) {
 2         stack<TreeNode*> st;
 3         vector<int> result;
 4         if (root == NULL) return result;
 5         st.push(root);
 6         while (!st.empty()) {
 7             TreeNode* node = st.top(); //中
 8             st.pop();
 9             result.push_back(node->val);
10             if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈），左
11             if (node->right) st.push(node->right); // 空节点不入栈，右
12         }
13         reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
14         return result;
15     }

     中序遍历（迭代法）代码：

     用一个指针从根节点开始一路向左，遍历到哪个节点后，如果这个节点没有左节点，就弹出当前节点，从中，右节点遍历.........如果有左节点的话，就继续一路向左。

 1 vector<int> inorderTraversal(TreeNode* root) {
 2         vector<int> result;
 3         stack<TreeNode*> st;
 4         TreeNode* cur = root;
 5         while (cur != NULL || !st.empty()) {
 6             if (cur != NULL) { // 指针来访问节点，访问到最底层
 7                 st.push(cur); // 将访问的节点放进栈
 8                 cur = cur->left;                // left是 左
 9             } else {
10                 cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
11                 st.pop();
12                 result.push_back(cur->val);     // 中
13                 cur = cur->right;               // 右
14             }
15         }
16         return result;
17     }