代码随想录训练营day14|LeetCode二叉树part1

@代码随想录@程序员Carl

原文讲解：第六章 二叉树part01 (qq.com)

快期末了，加速赶੭ ˙ᗜ˙ )੭

目录

理论基础

 二叉树的递归遍历(必须掌握)

 迭代遍历(比递归难不止一点)

---

理论基础

视频讲解：二叉树理论基础

文字讲解版：代码随想录 (programmercarl.com)

直接看视频就好了，2倍速15分钟，很详细。文字讲解字太多，看着头疼(快乐+99，智商-99)。

我自己不太了解的：

1.二叉搜索树不一定是完全二叉树，只要左右字数深度差不大于1就行。

2.要有意识地了解自己平常使用的容器，它的底层实现是怎样的。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间复杂度是logn；

unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。 

3.

4.⚝二叉树的定义，LeetCode不会让我们写：

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    //C++里一般要构造函数进行初始化
    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) {}
};

 二叉树的递归遍历(必须掌握)

视频讲解：LeetCode：144.前序遍历，145.后序遍历，94.中序遍历_哔哩哔哩_bilibili

LeetCode:144. 二叉树的前序遍历 

LeetCode:94. 二叉树的中序遍历 

LeetCode: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 *current,vector<int>& vector){
        if(current==nullptr) return;
        //中
        vector.push_back(current->val);    //易错点:忘记加->val
        //左
        traversal(current->left,vector);
        //右
        traversal(current->right,vector);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};

 中序遍历(左中右)，修改traversal函数就OK：

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

 后序遍历(左右中)，修改traversal函数：

void traversal(TreeNode* cur,vector<int>& vec){
        if(cur==nullptr) return;
        traversal(cur->left,vec);
        traversal(cur->right,vec);
        vec.push_back(cur->val);
    }

 迭代遍历(比递归难不止一点)

前序与后序：视屏讲解前序与后序遍历_哔哩哔哩_bilibili 

中序(比前后序难)：视屏讲解中序遍历 _哔哩哔哩_bilibili

中序的视频讲解代码有个错误，while的判断条件应该是||，而不是&&。

迭代遍历原文讲解：代码随想录 (programmercarl.com)

底层实现：栈。 LeetCode链接还是上面的144、94、145题。

注意：

1.因为栈是先进后出，所以前序遍历时右节点要比左节点先放入栈中，后序遍历相反。

2.最后两行代码是我的知识盲点，复习的时候看一下。

3.我老忘弹出栈元素，导致死循环。

前序和后序遍历：

//前序遍历
 
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        //易漏：root节点为空的情况
        if(root==nullptr) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node=st.top();
            st.pop();
            result.push_back(node->val);
            //右节点要比左节点先入栈，这和迭代法遍历二叉树的顺序相反
            if(node->right) st.push(node->right);    //右
            if(node->left) st.push(node->left);      //左
        }
        return result;
    }
};
 
 
//后序遍历
//改变两行代码的位置就行，如下：
if(node->left) st.push(node->left);      //左
if(node->right) st.push(node->right);    //右
 

中序遍历：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                st.pop();
                result.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

统一迭代法我还没看。 

二叉树终于入门了