每日算法题：Day 9

作者：TeddyZhang，公众号：算法工程师之路

Day 9, Python知识点走起~

1

编程题

【剑指Offer】树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路： 首先我们整理下这道题目的思路，首先我们去遍历二叉树A，然后去寻找与二叉树根节点相同的节点，这里我们也使用递归的方法！当找到相同节点后，我们再开始判断从这两个相同节点出发的两棵树是否为子树关系！

在判断时，仍然使用递归的思路去遍历，如果root2遍历完了，那么返回true，说明二叉树B是二叉树A的子树。如果root1遍历完了，则返回false，同时必须满足遍历的节点必须相同！

/*
 2struct TreeNode {
 3    int val;
 4    struct TreeNode *left;
 5    struct TreeNode *right;
 6    TreeNode(int x) :
 7            val(x), left(NULL), right(NULL) {
 8    }
 9};*/
class Solution {
public:
    bool isSubtree(TreeNode* root1, TreeNode* root2){
        if(root2 == nullptr)
            return true;
        if(root1 == nullptr)
            return false;
        return (root1->val == root2->val) && 
            isSubtree(root1->left, root2->left) && isSubtree(root1->right, root2->right);
    }

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
22    {
        if(pRoot1 == nullptr || pRoot2 == nullptr){
            return false;
        }
        bool result = false;
        if(pRoot1->val == pRoot2->val){
            result = isSubtree(pRoot1, pRoot2); 
        }
        if(!result){
            result = HasSubtree(pRoot1->left, pRoot2)
                  || HasSubtree(pRoot1->right, pRoot2);
        }
        return result;
    }
};

【剑指Offer】镜像二叉树

操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：源二叉树

8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5

思路： 这个使用递归的思路就很简单，一般二叉树用递归的方法很多，比如二叉树的遍历也可以使用递归的方法。我们首先交换左右子树的位置，因此使用tmp用于转换存储，然后递归转换就可以了！并且递归最重要的就是终止条件，这里的终止条件也很简单，递归到叶节点的儿子，则return，结束递归！

/*
 2struct TreeNode {
 3    int val;
 4    struct TreeNode *left;
 5    struct TreeNode *right;
 6    TreeNode(int x) :
 7            val(x), left(NULL), right(NULL) {
 8    }
 9};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot == nullptr)
            return;
        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

2

概念题

【Python】Python中的访问权限的修饰符怎么去表达public, private, protected关键字呢？

在CPP和JAVA中用于限定类中属性或者成员方法的访问权限，一般都可以使用public, private, protected关键字来表示。而Python没有这种关键字，但可以通过修饰符来表达！以属性name为例子，则有：

• name, 什么都不加默认为public方法
• _name, 单下划线，表示proctected方法，其只有类实例或者子类可以访问，在类外不能访问，因此不可以用“ from module import * ” 访问！
• __name, 双下划线，表示private方法，其只有类对象自己才能够访问，子类对象不能访问

但其实Python的私有化是一种伪私有化的方式，其__name不能访问，是由于Python自动将内部的__name改为_classname__name，因此我们再类外可以使用object._classname__name访问私有变量，但一般不要这么做！

【Python】进程、线程和协程的区别

进程拥有自己独立的堆和栈，既不共享堆，亦不共享栈，进程由操作系统调度。比如windows中两个应用程序APP！

线程拥有自己独立的栈和共享的堆，共享堆，不共享栈，线程亦由操作系统调度(标准线程)。

协程和线程一样共享堆，不共享栈，协程由程序员在协程的代码里显示调度。

进一步说，我们知道多个线程相对独立，有自己的上下文，切换受系统控制；而协程也相对独立，有自己的上下文，但是其切换由自己控制，由当前协程切换到其他协程由当前协程来控制。

【Python】Python中的数据类型都有哪些呢？

python中有六个标准数据类型，分别是数字（Number）,字符串（String）,列表（List）,元组（Tuple）,字典（Dictionary）,集合（Set）。

并且对于数字类型，则支持五种数字类型，分别是整型（int）,布尔型（bool）,双精度浮点型（float），复数（complex）,常整型（long）