C++牛客网编程(九)

C++牛客网编程(九),第1张

重建二叉树

描述
给定节点数为 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可能性

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562461.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-01
下一篇 2022-04-01

发表评论

登录后才能评论

评论列表(0条)

保存