C++牛客网编程（九）

重建二叉树

描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：n≤2000，节点的值 −10000≤val≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

思路：利用递归

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.empty()||vin.empty())
            return NULL;
        TreeNode* root=new TreeNode(pre[0]);
        int tmp=0;
        while(vin[tmp]!=pre[0]) tmp++;
        root->left=reConstructBinaryTree(vector<int>({pre.begin()+1,pre.begin()+1+tmp}),vector<int>({vin.begin(),vin.begin()+tmp}));
        root->right=reConstructBinaryTree(vector<int>({pre.begin()+1+tmp,pre.end()}),vector<int>({vin.begin()+tmp+1,vin.end()}));
        return root;
    }
};

重点：

1. 如何截取vector中的一段，并作为参数或者返回值
   vector({pre.begin()+1,pre.begin()+1+tmp})
2. 如何初始化treeNode，有点生疏了。
   

   
   

树的子结构

描述
输入两棵二叉树A，B，判断B是不是A的子结构。

（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
思路：如果返回真有三种可能性：全部相等，左子树包含，右子树包含。

而全部相等要检验每一个结点值。

class Solution {
public:
    bool isSame(TreeNode* p1, TreeNode* p2){
        if(!p2) return true;
        else if(!p1) return false;
        return p1->val==p2->val&&isSame(p1->left, p2->left)&&isSame(p1->right, p2->right);
    }
    
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2) return false;
        return isSame(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
    }
};

重点：

1. 起初第一个想法是利用前序遍历，再类似字符串kmp一样检测是否有相同序列。
   

   
   

   后来发现树因为有左右子树的原因，导致排序不同，所以不能这样想。
   

   
   

2. 通常对称性递归的返回值是多个条件的复合判断语句（参考其他同学想法）
   可能是以下几种条件判断的组合：
   节点非空的判断
   节点值比较判断
   (单树)调用根节点左右子树的递归函数进行递归判断
   (双树)调用两棵树的左右子树的递归函数进行判断

二叉树的镜像

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

数据范围：二叉树的节点数 0≤n≤10000， 二叉树每个节点的值 0≤val≤10000
要求： 空间复杂度 O(n)。

本题也有原地 *** 作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)
比如：
源二叉树

镜像二叉树

思路：DFS递归，每遇到一个结点就交换它的左右子树。

    TreeNode* Mirror(TreeNode* pRoot) {
        if(pRoot){
            TreeNode* tmp=NULL;
            tmp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=tmp;
            pRoot->left=Mirror(pRoot->left);
            pRoot->right=Mirror(pRoot->right);
        }
        return pRoot;
    }

重点：第一次写的时候忘了考虑根结点的NULL可能性