算法力扣刷题 三十五【二叉树基础和递归遍历】

前言

进入二叉树学习。
继续。

一、二叉树基础理论

理论篇——参考链接

以下是大纲：

二、遍历方式

学习递归法实现前、中、后遍历方法。

“输入”阶段

此处用了第一次递归法实现 根据题目的双指针操作，传递递归的参数。

解释递归

（1）递归：自己调用自己。重复执行一段代码，但是和循环有区别。
（2）过程：先传递，不到终止条件，继续传递；还不到终止条件，继续传递；……if判断到终止条件，开始return；返回上一层，从调用之后继续执行，结束后；再返回上一层，从调用自己之后继续执行，结束后；继续往上，直到第一层。

如何写好递归？

（1）前序遍历：

• 确定递归函数的参数和返回值：
  • 参数需要时可以再补充。一般需要传入root根节点和数组用来存放结果。
  • 返回值一般void。
• 确定终止条件：
  • if(cur == NULL) ，返回。
• 确定单层递归的逻辑：
  
  （2）中序和后序同理。

“输出”阶段

前序遍历题目：【144.二叉树的前序遍历】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& record){
        //终止条件
        if(cur == nullptr){
            return;
        }
        record.push_back(cur->val);//把根节点放入；
        traversal(cur->left,record);
        traversal(cur->right,record);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result); //返回到这一层，说明result已经放好结果。
        return result;

    }
};

中序遍历题目：【94.二叉树的中序遍历】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* cur,vector<int>& record){
        if(cur == nullptr){
            return;
        }
        traversal(cur->left,record);//先左子树
        record.push_back(cur->val);//再根节点
        traversal(cur->right,record);//再右子树
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};

后序遍历题目：【145.二叉树的后序遍历】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* cur,vector<int>& record){
        if(cur == nullptr){
            return;
        }
        traversal(cur->left,record);    //先左子树
        traversal(cur->right,record);   //再右子树
        record.push_back(cur->val);     //再放入根节点
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};

总结

• 为二叉树基础理论建立大纲：种类、遍历方式、存储结构。
• 递归算法学习。建立递归的模版，确定终止条件和逻辑；
• 二叉树前、中、后序遍历实现。

（欢迎指正，转载表明出处）