【代码随想录】学习笔记05-二叉树&【数基】对应部分

【代码随想录】学习笔记05-二叉树&【数基】对应部分

首先【https://cloud.tencent.com/developer/article/1591357】给到一个入门：

数据结构分为物理结构和逻辑结构，像数组这种数据结构就属于物理结构，人家是怎么样的就在内存中怎么存储，但是对于逻辑结构比如这里的二叉树，貌似就没法直接存了，不过逻辑结构的数据结构可以使用多种物理结构来存储。
一般来说，就是数组和链表，这俩万能啊，很多东东的底层貌似都有这俩货。所以对于二叉树也是一样的，可以使用链表和数组来存储。
一般我们都是用链式存储二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删 *** 作时间时间复杂度是logn，
unordered_map、unordered_map底层实现是哈希表。
所以大家使用自己熟悉的编程语言写算法，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等等，否则自己写的代码，自己对其性能分析都分析不清楚！

二叉树的定义代码：

 
 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) {}
 };

前中后序遍历：看中间节点，用递归方法

144.二叉树的前序遍历 1.递归法： 2.非递归法的前中后序遍历※都还没看※见代随

class Solution{
public:
void preorder(TreeNode* root, vector& res){//基本 *** 作之：vector作参数要加&
    if (root == NULL) return;
    //vector:push_back, 栈: push
    //链表：->val，栈：top()
        res.push_back(root->val);
        preorder( root->left, res);
        preorder( root->right, res);
}
vector preorderTraversal( TreeNode* root){//此处只有一个参数!
        vector  res;
        preorder(root, res);  //非常错误表述！result = preorder(root, res);
        return res;
    }
//也可以改成只有class里只有一个vector类型的函数，在104题中可见是【代】自身编程习惯
};

//  //某个评论里的回答
// class Solution {
// public:
//     vector preorderTraversal(TreeNode* root) {
//         vector ans;
//         stack s;
//         s.push(root);
//         while(!s.empty()){
//             TreeNode* r=s.top();
//             s.pop();
//             if(!r) continue;
//             ans.push_back(r->val);
//             s.push(r->right);
//             s.push(r->left);     
//         }
//         return ans;
//     }
// };
// // 需要先默写一下构造函数的代码！

102.二叉树的层序遍历

【代】&【扣】推荐方法均为迭代+队列:

class Solution{
public:
vector > levelOrder(TreeNode* root){
    vector > ret;
    if(!root)return ret;
    //注意树为空的表述！根节点为空：(!root)
    //也可以用：(root == nullptr)【见题104】
    queue   q;
    q.push(root);//输入冰山，其顶部为root，是把二叉树的全部以根节点root为标志放进去
    while(!q.empty()){
        int currentLevelSize = q.size();
        ret.push_back(vector());//注意新增空vector()的表述
        for(int i = 1; i <= currentLevelSize; i++){
            TreeNode* node = q.front();//只取最顶部，无参数   auto！？
            q.pop();
            ret.back().push_back(node->val);//注意..中间的back()函数也是需要括号的
            if(node->left) q.push(node->left);//再次注意树为空的表述，不用empty函数
            if(node->right) q.push(node->right);
        }


    }
return ret;//非void函数，一开始必须给予定义，最后必须给予返回！！！
}
};

批注：这道题的理解花了很久时间，最后几乎句句cout测试才大致理解并默写出来，但是最后一个for循环之后理应已经达不到while的条件，却为何又循环了一遍？只能留给以后再遇到这道题的自己为现在的我解答了。。。

今天发现，这个题解的思路属于【广度优先算法】(BFS)，和以下的BFS基本结构也很相似了

  
bool BFS(Node& Vs, Node& Vd){  
    queue Q;  
    Node Vn, Vw;  
    int i;  

    //初始状态将起点放进队列Q  
    Q.push(Vs);  
    hash(Vw) = true;//设置节点已经访问过了！  

    while (!Q.empty()){//队列不为空，继续搜索！  
        //取出队列的头Vn  
        Vn = Q.front();  

        //从队列中移除  
        Q.pop();  

        while(Vw = Vn通过某规则能够到达的节点){  
            if (Vw == Vd){//找到终点了！  
                //把路径记录，这里没给出解法  
                return true;//返回  
            }  

            if (isValid(Vw) && !visit[Vw]){  
                //Vw是一个合法的节点并且为白色节点  
                Q.push(Vw);//加入队列Q  
                hash(Vw) = true;//设置节点颜色  
            }  
        }  
    }  
    return false;//无解  
}  

104.二叉树的最大深度

两种思路：
DFS深度优先-递归
BFS广度优先-迭代
以下是DFS方法，代随里还给了递归中的前序（不理解里面呢的回溯处理）、后序和BFS

class Solution{
    public:
    int maxDepth(TreeNode* root){
        if (!root) return 0;
        int depth;

        return (max(maxDepth(root->left), maxDepth(root->right)) +1);
    }
};

101.对称二叉树

//【代随】的做法
// class Solution {
// public:
//     bool compare(TreeNode* left, TreeNode* right) {
//         // 首先排除空节点的情况
//         if (left == NULL && right != NULL) return false;
//         else if (left != NULL && right == NULL) return false;
//         else if (left == NULL && right == NULL) return true;
//         // 排除了空节点，再排除数值不相同的情况
//         else if (left->val != right->val) return false;

//         // 此时就是：左右节点都不为空，且数值相同的情况
//         // 此时才做递归，做下一层的判断
//         bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
//         bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
//         bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
//         return isSame;

//     }
//     bool isSymmetric(TreeNode* root) {   
//写成两个函数，对这道题是优选，【力扣】也是如此，因为递归思路用两个变量合适，但题目只有一个参数root
//         if (root == NULL) return true;
//         return compare(root->left, root->right);//或者写成(root, root)
//     }
// };
//【力扣】的做法，异曲同工
class Solution{
    public:
    bool check(TreeNode* p, TreeNode* q){
        if (!p && !q) return true;
        else if (!p || !q) return false;
        else return(p->val == q->val) && check (p->left, q->right) && check (p->right, q->left);

    }
    bool isSymmetric(TreeNode* root){
        return check(root, root);
    }
};