Complete Binary Tree Inserter（C++完全二叉树插入器）

桃扇骨 2023-01-16 09:43 140阅读 0赞

解题思路：

（1）利用完全二叉树的性质

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class CBTInserter {
    private:
        vector<TreeNode*> vec;
    public:
        CBTInserter(TreeNode* root) {
            vec.push_back(root);
            for(int i=0;i<vec.size();i++) {
                if(vec[i]->left) vec.push_back(vec[i]->left);
                if(vec[i]->right) vec.push_back(vec[i]->right);
            }
        }
        
        int insert(int v) {
            int n=vec.size();
            TreeNode *p=new TreeNode(v);
            vec.push_back(p);
            if(n%2==0) vec[(n-1)/2]->right=p;
            else vec[(n-1)/2]->left=p;
            return vec[(n-1)/2]->val;
        }
        
        TreeNode* get_root() {
            return vec[0];
        }
    };
    
    /**
     * Your CBTInserter object will be instantiated and called as such:
     * CBTInserter* obj = new CBTInserter(root);
     * int param_1 = obj->insert(v);
     * TreeNode* param_2 = obj->get_root();
     */

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT（甲级）1110 Complete Binary Tree (25point(s)) 判断是不是完全二叉树

题目题目链接思路题目大意：给一颗二叉树，判断是不是完全二叉树；可以根据完全二叉树的性质来判断，在线性存储结构下，左孩子下标 = 2 * 父节点，右孩子下标 = 2 * ...

ゝ一世哀愁。/ 2024年05月08日 06:03/ 0 赞/ 59 阅读

相关 1110 Complete Binary Tree (25 分) 判断是否为一棵完全二叉树

iven a tree, you are supposed to tell if it is a complete binary tree. Input Specif...

缺乏、安全感/ 2024年04月17日 21:28/ 0 赞/ 59 阅读

相关 Complete Binary Tree Inserter（C++完全二叉树插入器）

解题思路：（1）利用完全二叉树的性质 / Definition for a binary tree node. struct TreeNo

桃扇骨/ 2023年01月16日 09:43/ 0 赞/ 141 阅读

相关【数据结构】二叉树(Binary Tree)

目录 1 树的概念 1.1 树的定义 1.2 相关概念 2 二叉树的概念 2.1 二叉树的定义 2.2 二

末蓝、/ 2022年12月08日 04:58/ 0 赞/ 187 阅读

相关二叉搜索树（binary search tree）

定义二叉搜索树：二叉树中任何节点的键值一定大于其左子树中每一个节点的键值，并且小于其右子树中每一个节点的键值。查找基于此，在二叉搜索树中搜索最小元素和最大元

电玩女神/ 2022年08月08日 14:39/ 0 赞/ 143 阅读

相关线索二叉树（Binary Thread Tree）

1.概念按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。在改序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结

逃离我推掉我的手/ 2022年06月15日 09:55/ 0 赞/ 154 阅读

相关 (PAT 1110) Complete Binary Tree (判断完全二叉树)

Given a tree, you are supposed to tell if it is a complete binary tree. Input Specific

雨点打透心脏的1/2处/ 2022年04月23日 05:54/ 0 赞/ 139 阅读

相关 1110 Complete Binary Tree（完全二叉树）

题意：给出一个n表示有n个结点，这n个结点为0~n-1，给出这n个结点的左右孩子，求问这棵树是不是完全二叉树思路：这题就是先建树，找出根结点然后层序遍历，我

痛定思痛。/ 2021年12月20日 23:11/ 0 赞/ 183 阅读

相关二叉查找树（Binary Search Tree）

Date：2019-06-25 14:40:32 基本操作注意：数据量较大时，插入建树的时间复杂度会很高，慎用！ 1 //查找 2 vo

深碍√TFBOYSˉ_/ 2021年12月20日 06:29/ 0 赞/ 212 阅读

相关 PAT A1064 Complete Binary Search Tree [完全二叉搜索树]

题目描述 [链接][Link 1] 给一串构成树的序列，已知该树是完全二叉搜索树，求它的层序遍历的序列分析二叉搜索树的性质：左子树<根<右子树，而中

「爱情、让人受尽委屈。」/ 2021年10月23日 09:51/ 0 赞/ 240 阅读