剑指offer刷题记录--树

1. JZ55 二叉树的深度

1. 递归（后序遍历，，无法用栈）

使用递归方法对每个结点进行递归，直到找到叶子节点，层层返回，每一层+1，最终即得树的深度。
（这个遍历方式是后序遍历）
动图

//使用链表来存储二叉树
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return 0;
        return max( TreeDepth(pRoot->left), TreeDepth(pRoot->right) )+1;
    }
};

2. 层序遍历（队列）

求树的层数就想到了层序遍历的方法，由于队列中的元素个数是可知的，所以循环把本层的元素处理完即可，统计二叉树层数需要在每一层内进行循环，但是如果是按照层序遍历的顺序打印元素就不需要分层循环了。

//使用层序遍历来统计层数，由于每层的节点个数n可以统计出来，那就循环n次，把队列中n个节点都出队，同时将其子节点入队。
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        TreeNode* FrontNode(nullptr);
        queue que;
        int Res=0;
        if(pRoot==nullptr)
            return 0;
        que.push(pRoot);
        while(!que.empty())
        {
            ++Res;
            size_t n = que.size();  //统计本层的节点个数
            for(size_t i=0; i
                FrontNode = que.front();
                que.pop();
                if(FrontNode->left)
                    que.push(FrontNode->left);
                if(FrontNode->right)
                    que.push(FrontNode->right);
            }
        }
        return Res;
    }
};

3. 本题小结

1. 统计树的深度可以使用递归的方法，后序遍历。
2. 也可以使用队列层序遍历，在对一层的队列元素进行处理之前可以先统计本层的元素个数，然后在循环中处理本层所有节点，然后深度++，最后进入下一层的处理。

2. JZ27 二叉树的镜像

1. 递归

在前向递归的时候就交换左右结点，依次迭代直到叶子节点，就完成了镜像。

//递归法
class Solution {
public:
    
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==nullptr)
            return pRoot;
        TreeNode* TmpNode = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = TmpNode;
        pRoot->left = Mirror(pRoot->left);
        pRoot->right = Mirror(pRoot->right);
        return pRoot;
    }
};

2. 栈

在树中，凡是能用递归的都能用栈。
由于先对左右结点入栈，然后再交换左右结点，所以相当于是在原来的树上的右侧开始处理，堆栈保证了在出栈时一个右结点，一个左节点地处理。

//栈法
class Solution {
public:
    
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==nullptr)
            return pRoot;
        stack sta1;
        sta1.push(pRoot);
        while(!sta1.empty())
        {
            TreeNode* TopNode = sta1.top();
            sta1.pop();
            if(TopNode->left)
                sta1.push(TopNode->left);
            if(TopNode->right)
                sta1.push(TopNode->right);
            TreeNode* TmpNode = TopNode->left;
            TopNode->left = TopNode->right;
            TopNode->right = TmpNode;
        }
        return pRoot;
    }
};

3. 本题小结

1. 二叉树的镜像用递归比较简单；
2. 二叉树中能用递归的大多数也能用栈，求深度不行，因为求深度如果不递归的话就得处理一层中所有的结点，但是对于已经在栈中的元素，出了栈之后就得立即处理，但是由于栈式LIFO，新入栈的就不是这一层的了，所以不能用栈。

3. JZ28 对称的二叉树（有些难）

这题本身之前想用双向队列deque进行层序遍历，每次将deque中的front()和back()出队比较其值，其实想想这样也可以做。后面尝试一下

1. 层序遍历

不用严格控制每层，即不用设置一层的for循环，原理是如果对称的话，遍历每一层的数据会形成回文，所以管理两个相对的队列，一个从左，一个从右，空指针也要算，否则可能会因为空指针位置不同而导致不同的结构，就不对称了。

//使用层序遍历判断，使用deque
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return true; 
        queue quel;  //左便利
        queue quer;  //右遍历
        quel.push(pRoot->left);
        quer.push(pRoot->right); 
        while(!quel.empty() && !quer.empty())
        {
                TreeNode * LeftFront = quel.front();
                TreeNode * RightFront = quer.front();
                quel.pop();
                quer.pop();
                
                //同时为空就不插入了，就能检测到退出了
                if(LeftFront==nullptr && RightFront==nullptr)  
                    continue;
                
                if((LeftFront==nullptr || RightFront==nullptr) || (LeftFront->val!=RightFront->val))
                    return false;
                //从左往右 
                quel.push(LeftFront->left);
                quel.push(LeftFront->right);
                //从右往左
                quer.push(RightFront->right);
                quer.push(RightFront->left);
        }
        return true;
    }
};

2. 递归(推荐)

思路：前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。

递归主要把握住：条递逻。
终止条件：当二者都为nullptr证明到了叶子节点，返回true；当二者不是同时为nullptr或者二者的val不相等，则必定不对称，返回false。
递归调用：因为是“根左右”和“根右左”的递归，所以递归的 “左对右”&“右对左” 。
逻辑处理：此题没有什么逻辑处理（链表反转那题在正向时要反转指针，属于逻辑处理，此题没有）。

//使用层序遍历判断，使用deque
class Solution {
public:
    //先序遍历和逆先序遍历
    bool recursion(TreeNode* root1, TreeNode* root2)
    {
        //可以两个都为空
        if(root1==nullptr && root2==nullptr)
            return true;
        //只有一个为空或者节点值不同，必定不对称
        if(root1==nullptr || root2==nullptr || root1->val!=root2->val)
            return false;
        //每层对应的节点进入递归，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边
        return recursion(root1->left, root2->right) && recursion(root1->right, root2->left);
    }
    bool isSymmetrical(TreeNode* pRoot) {
        return recursion(pRoot, pRoot);
    }
};

4. JZ79 判断是不是平衡二叉树

1. 自顶向下递归（推荐）

空间复杂度O(n)，递归的栈；时间复杂度 O ( n 2 ) O(n^2) O(n2)，最坏情况每个结点都要递归IsBalanced_Solution()函数，每个IsBalanced_Solution(0里面是O(n)，所以是 O ( n 2 ) O(n^2) O(n2).

这个我做的时候忘了对每个子树都要递归调用IsBalanced_Solution()，可能出现两遍都是两个链表一样的子树，显然不是平衡的。

//自顶向下法，先获得深度再根据深度判断是否平衡
class Solution {
public:
    int recursion(TreeNode* root)
    {
        if(root==nullptr)
            return 0;
        return max(recursion(root->left), recursion(root->right))+1;
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==nullptr)
            return true; 
        int HLeft = recursion(pRoot->left);
        int HRight = recursion(pRoot->right);
        if(abs(HLeft - HRight)>1)
            return false;
        return IsBalanced_Solution(pRoot->left) &  IsBalanced_Solution(pRoot->right);  //每一个子树都要判断其是否平衡
    }
};

2. 自底向上法

在第一步递归的基础上添加一些判断的代码即可得这个版本，但是有些难理解。

//自底向上法，从底部的子树开始判断，如果子树不平衡，直接返回false，不用再判断
class Solution {
public:
    bool recursion(TreeNode* root, int& depth)  //条递逻
    {
        if(root==nullptr)
        {
            depth=0;
            return true;
        }
        int LDepth = 0;
        int RDepth = 0;
        if(recursion(root->left, LDepth)==false || recursion(root->right, RDepth) == false)
            return false;
        // 判断深度查是否大于1
        if(abs(LDepth-RDepth)>1)
            return false;
        depth = max(LDepth, RDepth)+1;
        return true;
    }
    
    bool IsBalanced_Solution(TreeNode* pRoot) 
    {
        if(pRoot==nullptr)
            return true;
        int depth = 0;
        return recursion(pRoot, depth);  //每一个子树都要判断其是否平衡
        
    }
};

3. 本题小结

自顶向下递归虽然时间复杂度高，但是容易理解，因为计算深度和判断平衡是分开进行的（注意对每个子树都要递归判断是否平衡，避免左右链表得情况）；而自底向上法将这两项工作融合在一起，理解起来有些难。

5. JZ77 按之字形顺序打印二叉树

1. 使用双端队列deque（推荐）

时间空间复杂度均为O(N)
很好理解，只需要额外维护一个布尔类型的flag，为true时从对头输出，从左到右入队尾；为false时从队尾输出，从右到左入队头。注意结果是一个二维vector

//考虑层序遍历，双向队列，单层（True）从左到右，双层（false）从右到左。
class Solution {
public:
    vector > Print(TreeNode* pRoot) {
        bool LayerFlag(true);
        deque deq;

        vector > ResVec;
        if(pRoot==nullptr)
            return ResVec;
        deq.push_back(pRoot);
        while(!deq.empty())
        {
            vector ResTmp;
            int n = deq.size();
            //单层从左到右
            if(LayerFlag)
            {
                LayerFlag = false;
                for(int i=0; i
                    TreeNode* TmpNode = deq.front();
                    ResTmp.push_back(TmpNode->val);
                    deq.pop_front();
                    if(TmpNode->left)     deq.push_back(TmpNode->left);
                    if(TmpNode->right)    deq.push_back(TmpNode->right);
                }
                ResVec.push_back(ResTmp);
            }
            //双层从右到左
            else
            {
                LayerFlag = true;
                for(int i=0; i
                    TreeNode* TmpNode = deq.back();
                    ResTmp.push_back(TmpNode->val);
                    deq.pop_back();
                    if(TmpNode->right)     deq.push_front(TmpNode->right);
                    if(TmpNode->left)      deq.push_front(TmpNode->left);
                }
                ResVec.push_back(ResTmp);
            }
        }
        return ResVec;
    }
};

2. 官方解析1—普通队列

时间空间复杂度均为O(N)
使用普通队列，维护一个层数变量level，出队正常从front出，但是插入到二维Result vector中根据层数判断是push_back还是insert(begin)，如此实现之字输出。

class Solution {
public:
    vector > Print(TreeNode* pRoot) {
        vector > res; 
        if (!pRoot)
            return res; 
        queue q; // 定义队列
        q.push(pRoot); // 根结点入队列
        int level = 0;
        while (!q.empty()) {
            vector arr; // 定义数组存储每一行结果
            int size = q.size(); // 当前队列长度
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = q.front(); // 队头元素
                q.pop(); 
                if (!tmp) // 空元素跳过
                    continue;
                q.push(tmp->left); // 左孩子入队列
                q.push(tmp->right); // 右孩子入队列
                if (level % 2 == 0) {
                    // 从左至右打印
                    arr.push_back(tmp->val);
                } else { // 从右至左打印
                    arr.insert(arr.begin(), tmp->val);
                }
            }
            level++; // 下一层，改变打印方向
            if (!arr.empty())
                res.push_back(arr); // 放入最终结果
        }
        return res;
    }

};

3. 官方解析2—双堆栈

时间空间复杂度均为O(N)，维护两个堆栈，根据不同层决定从左往右入栈还是从右往左入栈，对于结果都是push_back()

class Solution {
public:
    vector > Print(TreeNode* pRoot) {
        vector > res; 
        if (!pRoot) 
            return res; 
        stack stk1, stk2; // 定义两个栈
        stk1.push(pRoot); // 根结点入栈
        while (!stk1.empty() || !stk2.empty()) { // 两个栈全空时循环结束
            vector  arr; 
            while (!stk1.empty()) {
                TreeNode* p = stk1.top(); 
                stk1.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->left) stk2.push(p->left); // 左孩子入栈
                if (p->right) stk2.push(p->right); // 右孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
            arr.clear(); // 清空
            while (!stk2.empty()) {
                TreeNode* p = stk2.top(); 
                stk2.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->right) stk1.push(p->right); // 右孩子入栈
                if (p->left) stk1.push(p->left); // 左孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
        }
        return res;
    }
};

4. 本题小结

使用双向队列deque直观，代码也好写，只需注意出队和入队的方向。

6. JZ32 从上往下打印二叉树(简单) 1. 层序遍历(推荐)

// 层次遍历二叉树
class Solution {
public:

    vector PrintFromTopToBottom(TreeNode* root) {
        vector ResVec;
        queue que;
        if(root==nullptr)
            return ResVec;
        que.push(root);
        while(!que.empty())
        {
            TreeNode* TmpNode = que.front();
            que.pop();
            ResVec.push_back(TmpNode->val);
            if(TmpNode->left)  que.push(TmpNode->left);
            if(TmpNode->right)  que.push(TmpNode->right);
        }
        return ResVec;
    }
};

2. 官方基于递归的层序遍历

实际上是先将所有数据按照层次为第一下标存在一个二维vector中，然后遍历二维vector存到1维vector中，有些麻烦，看看思路即可。

class Solution {
public:
    void traverse(TreeNode* root, vector>& res, int depth) {
        if(root){
            //新的一层
            if(res.size() < depth) 
                res.push_back(vector{});
            //vector从0开始计数因此减1，在节点当前层的vector中插入节点
            res[depth - 1].push_back(root->val);
        }
        else
            return;
        //递归左右时进入下一层
        traverse(root->left, res, depth + 1);
        traverse(root->right, res, depth + 1);
    }
     
    vector PrintFromTopToBottom(TreeNode* root) {
        vector res;
        vector > temp;
        if(root == NULL)
            //如果是空，则直接返回空vector
            return res;
        traverse(root, temp, 1);
        //送入一维数组
        for(int i = 0; i < temp.size(); i++)
            for(int j = 0; j < temp[i].size(); j++)
                res.push_back(temp[i][j]);
        return res;
    }
};

7. JZ54 二叉搜索树的第k个节点

1. 使用vector

使用中序遍历，依次将节点push_back()到vector中，检查元素个数，到k就停止插入，然后输出。

    //随时检查vec是否符合对应的节点个数
    void MidRecursion(TreeNode* root, int k, vector& vec)
    {
        if(root==nullptr || vec.size()==k)  return;
        MidRecursion(root->left, k, vec);
        //只插入到等于k时
        if(vec.size()val);
        MidRecursion(root->right, k, vec);
    }
    
    //返回的是节点值
    int KthNode(TreeNode* proot, int k) {
        // write code here
        vector vec;
        if(k==0) return -1;
        MidRecursion(proot, k, vec);
        if(vec.size()==k) return vec[k-1];
        else return -1;
    }

2. 官方给的直接使用count

不用push_back()，直接管理一个计数器count，到达k就停止遍历，然后输出，注意如果不定义成员变TreeNode* Res（nullptr）的话，需要传入指针的引用TreeNode*& Res，否则默认初始化的指针是空指针，一直报错。

    void MidRecursion(TreeNode* root, int& count, int k, TreeNode*& res)
    {
        if(root==nullptr || count==k)  
            return;
        MidRecursion(root->left, count, k, res);
        ++count;
        if (count==k) 
            res = root;
        MidRecursion(root->right, count, k, res);
    }
    
    //返回的是节点值
    int KthNode(TreeNode* proot, int k) {
        // write code here
        vector vec;
        int count=0;
        TreeNode* Res = nullptr;
        MidRecursion(proot, count, k, Res);
        if(Res) return Res->val;
        else return -1;
    }

3. 官方使用栈进行中序遍历

这个不太好写，还是递归比较方便。这个思想是先从左子树开始到底，到底之后转到右子树，再左子树到底，再转到右子树，直到找到够k个为止。

class Solution {
public:
    int KthNode(TreeNode* proot, int k) {
        if(proot == NULL)
            return -1;
        //记录遍历了多少个数
        int count = 0;  
        TreeNode* p = NULL;
        //用栈辅助建立中序
        stack s;   
        while(!s.empty() || proot != NULL){
            while (proot != NULL) {
                s.push(proot);
                //中序遍历每棵子树从最左开始
                proot = proot->left;   
            }
            p = s.top();
            s.pop();
            count++;
            //第k个直接返回
            if(count == k)
                return p->val;
            proot = p->right;
        }
        //没有找到
        return -1;
    }
};

4. 本题小结

1. 先序，中序，后序遍历都是在根节点处进行操作，比如这里的++count。

8. JZ68 二叉搜索树的最近公共祖先

1. 自己的层序遍历搜索法

空间复杂度 O ( N ) O(N) O(N)，时间复杂度 O ( N ) O(N) O(N)。
思路：

1. 先使用层序遍历将所有的结点值存入一个vector>中，
2. 再求得p和q的深度，根据深度是否相同来搜索，
3. 相同时从其所在的层的上一层开始搜索，找其父节点，直到找到相同父节点为止；
4. 若深度不同则从较深的一层开始找，直到找到相同的层，如果找到的父节点是相同的，则返回，如果不同则根据3的思路来查找。

在过程3中最坏的情况是最底层的两个结点，其唯一公共父节点是最上层的根节点，需要遍历所有结点才能找到，时间复杂度O(N)；引入了额外的vector>，空间复杂度O(N).

//空间复杂度O(N)，时间复杂度O(N^2)
class Solution {
public:
    
    
    void LayerTraverse(TreeNode* root, int& layer, vector>& Vec)
    {
        queue que;
        if(root==nullptr) return;
        que.push(root);
        while(!que.empty())
        {
            //层数递增
            ++layer;
            //本层数据个数
            int n = que.size();
            map TmpMap;
            for(int i=0; i
                TreeNode* TmpNode=que.front();
                que.pop();    
                TmpMap[TmpNode->val] = TmpNode;
                if(TmpNode->left) que.push(TmpNode->left);
                if(TmpNode->right) que.push(TmpNode->right);
            }
            //本层数据入vector
            Vec.push_back(TmpMap);
        }
    }
    
    //在相同层的遍历上查找共同祖先， 
    //@param  layer  待查的数据所在的层数
    int FindInSameLayer(vector>& Vec, int& layer, int p, int q)
    {
        //到了同一层，仍然不是本身，那就继续往上在每一层中找
        for(int i=layer-1; i>=0; --i)
        {
            for(auto each:Vec[i])
            {
                int TmpVal = -1;
                if(each.second->left)
                {
                    TmpVal = each.second->left->val;
                    if(TmpVal==p) p = each.first;
                    if(TmpVal==q) q = each.first;
                }
                if(each.second->right)
                {
                    TmpVal = each.second->right->val;
                    if(TmpVal==p) p = each.first;
                    if(TmpVal==q) q = each.first;
                }
                if(p==q)  return p;
            }
        }
        return -1;
    }
    
    //使用层序遍历将数据全部存入vector > >中便于查找
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if(p==q) return p;
        int layer = -1;
        int Res = -1;
        vector> Vec;
        LayerTraverse(root, layer, Vec);
        //求p，q深度
        int DP=0;
        int DQ=0;
        for(int i=0; i
            //根据first的值来找
            if(Vec[i].find(p)!=Vec[i].end())   DP = i;
            if(Vec[i].find(q)!=Vec[i].end())   DQ = i;
        }
        //若p，q深度相同，分别找到上一层的祖先，如果相同则结束查找，如果不同继续往上查找
        if(DP==DQ)
        {
            Res = FindInSameLayer(Vec, layer, p, q);
            if(Res!=-1) return Res;
        }
        
        // 深度不相同时先从更深的往上找，直到找到同一深度。
        int TMP_Anc = -1;
        int max_layear = (DP>DQ)? DP:DQ;
        int min_layear = (DPDQ)? p:q;
        int ToComparedVal = (DP=min_layear; --i)
            for(auto each:Vec[i])
            {
                int TmpVal = -1;
                if(each.second->left)
                {
                    TmpVal = each.second->left->val;
                    if(TmpVal==ToFindVal) ToFindVal = each.first;
                }
                if(each.second->right)
                {
                    TmpVal = each.second->right->val;
                    if(TmpVal==ToFindVal) ToFindVal = each.first;
                }
                if(ToFindVal==ToComparedVal) return ToFindVal;  //往上找找到了本身就是最近祖先节点
            }
        
        //到了同一层，仍然不是本身，那就继续往上在每一层中找      
        Res = FindInSameLayer(Vec, min_layear, ToFindVal, ToComparedVal);
        if(Res!=-1) return Res;
        
        return -1;
    }
};

2. 官方1–路径搜索比较（推荐）

空间复杂度 O ( N ) O(N) O(N)，时间复杂度 O ( N ) O(N) O(N)
思路：分别找到从根节点到p和q的路径，比较路径，最后一个相同的路径点就是最近祖先节点。
最坏情况是一个链表式的二叉比较树，存放路径，空间复杂度 O ( N ) O(N) O(N)，只有最初的根节点式共同祖先，时间复杂度 O ( N ) O(N) O(N)

//空间复杂度O(N)，时间复杂度O(N)
class Solution {
public:
    
    
    //获得路径
    void GetPath(TreeNode* root, int target, vector& ResVec)
    {
        TreeNode* TmpNode(root);
        while(TmpNode->val!=target)
        {
            ResVec.push_back(TmpNode->val);
            if(TmpNode->val > target)
                TmpNode = TmpNode->left;
            else
                TmpNode = TmpNode->right;
        }
        ResVec.push_back(target);
    }
    
    //使用层序遍历将数据全部存入vector > >中便于查找
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        int Res=-1;
        vector PathP;
        vector PathQ;
        GetPath(root, p, PathP);
        GetPath(root, q, PathQ);
        int Short = (PathP.size()
            if(PathP[i]==PathQ[i])
            {
                Res = PathP[i];
            }
            else break;
        }
        return Res;
    }
};

3. 官方–2一次遍历法（更推荐）

分析是王道：二叉查找树的特征是左<根<右，所以如果 此根节点值大于一个小于另一个，则此根节点必定是最近的公共父节点，如果此节点均大于两值，则要找的点必定在左子树上，往左递归即可，如果均小于，则必在右子树上，往右递归即可。
这就是二分查找的原型，时间复杂度 O ( l o g ( N ) ) O(log(N)) O(log(N))，空间复杂度 O ( N ) O(N) O(N)(这个不太确定)。

//空间复杂度O(N)，时间复杂度O(log(N))
class Solution {
public:
    
    
    //递归调用
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        // write code here
        if( ((root->val >= p) && (root->val <= q)) || (root->val <= p) && (root->val >= q) )
            return root->val;
        else if(root->val>=p && root->val>=q)
            return lowestCommonAncestor(root->left, p, q);
        else 
            return lowestCommonAncestor(root->right, p, q);
    }
};

4. 小结

1. （最推荐）最推荐的方法是一边遍历递归，跟据分析，结果只能在一个大于，一个小于的节点处。
2. （次推荐）根据左<根<右的特征可以找到 p p p和 q q q的路径，两个路径最后一个相同的值就是结果。

9. JZ26 树的子结构

1. 递归先序遍历（推荐）

思路：先找到A中与B的根节点值相同的结点；根据已找到的头结点为地址，同时先序遍历A和B，比较数值是否相同，如果最后都相同，那么B为A的子树，有一个不相同则不是子树。
复杂度分析：时间复杂度： O ( m n ) O(mn) O(mn)， m m m和 n n n分别是AB树的节点个数，最坏情况下，B为aab形式，A中结点只有一个b剩下全是a，所以要在A按照B的顺序遍历m次，最后才找到匹配的aab，所以是 O ( m n ) O(mn) O(mn)，实际上求相同根节点可以和后面的前序遍历查找融合在一起，但是这样显得代码混乱，不易读懂。

官方方法和我的思路相同，这里就不贴官方的代码了。

//递归解决，在每个递归中只判断根，利用先序遍历来递归
class Solution {
public:
    bool PreTraverse(TreeNode* root1, TreeNode* root2)
    {
        bool Res(false);
        if(root2==nullptr)
            return true;
        else if(root2!=nullptr && root1==nullptr)
            return false;
        else if(root1->val!=root2->val)
            return false;
        Res = PreTraverse(root1->left, root2->left);
        if(Res==false) return false;
        Res = PreTraverse(root1->right, root2->right);
        return Res;
    }
    
    void FindRoot(TreeNode* root, int TargetVal, vector& RootVec)
    {
        if(root)
        {
            if(root->val==TargetVal)
                RootVec.push_back(root);
            FindRoot(root->left, TargetVal, RootVec);
            FindRoot(root->right, TargetVal, RootVec);
        }
    }
    
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(pRoot1==nullptr || pRoot2==nullptr)
            return false;
        vector RootVec;
        FindRoot(pRoot1, pRoot2->val, RootVec);  //在A中找到与B根节点相同的根节点
        bool Res(false);
        for(auto EachRoot:RootVec)
        {
            Res = PreTraverse(EachRoot, pRoot2);
            if(Res==true) 
                return true;  //有一个就算有
        }
        return false;
    }
};

2. 两次层次遍历

思想是借助队列方法1中的先序遍历替换为层次遍历，其余一样。将A先进行层次遍历，找到B的头结点，找到之后就以这个结点为头节点来层次遍历这棵树，与B比较。

class Solution {
public:
    //层次遍历判断两个树是否相同
    bool helper(TreeNode* root1, TreeNode* root2){ 
        queue q1, q2;
        q1.push(root1);
        q2.push(root2);
        //以树2为基础，树1跟随就可以了
        while(!q2.empty()){ 
            TreeNode* node1 = q1.front(); 
            TreeNode* node2 = q2.front();
            q1.pop();
            q2.pop();
            //树1为空或者二者不相等
            if(node1 == NULL || node1->val != node2->val) 
                return false;
            //树2还有左子树
            if(node2->left){ 
                //子树入队
                q1.push(node1->left); 
                q2.push(node2->left);
            }
            //树2还有右子树
            if(node2->right){ 
                //子树入队
                q1.push(node1->right); 
                q2.push(node2->right);
            }
        }
        return true;
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //空树不为子结构
        if(pRoot1 == NULL || pRoot2 == NULL) 
            return false;
        queue q;
        q.push(pRoot1);
        //层次遍历树1
        while(!q.empty()){ 
            TreeNode* node = q.front();
            q.pop();
            //遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
            if(node->val == pRoot2->val){ 
                if(helper(node, pRoot2))
                    return true;
            }
            //左子树入队
            if(node->left) 
                q.push(node->left);
            //右子树入队
            if(node->right) 
                q.push(node->right);
        }
        return false;
    }
};

3. 本题小结

1. 查找B树是否为A的子树，需要两步：1. 先序遍历在A中找到与B的头节点值相同的所有结点 2.对于每个扎到的节点，先序遍历对比AB子树是否相同，只要有一个相同就算是找到了。