919.完全二叉树插入器

链接：919.完全二叉树插入器
难度：Medium
标签：树、广度优先搜索、设计、二叉树
简介：设计一种算法，将一个新节点插入到一个完整的二叉树中，并在插入后保持其完整。

题解 1 - cpp

• 编辑时间：2022-07-25
• 内存消耗：2.1MB
• 编程语言：cpp
• 解法介绍：利用完全二叉树特性，列表快速查找父亲。

class CBTInserter {
   public:
    TreeNode* root;
    vector<TreeNode*> list;
    CBTInserter(TreeNode* _root) {
        this->root = _root;
        queue<TreeNode*> q;
        q.push(root);
        list.push_back(root);
        while (q.size()) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
                list.push_back(node->left);
            }
            if (node->right) {
                q.push(node->right);
                list.push_back(node->right);
            }
        }
    }
    int insert(int val) {
        int idx = list.size(), pidx = idx / 2 - (idx & 1 ? 0 : 1);
        list.push_back(new TreeNode(val));
        if (idx & 1)
            list[pidx]->left = list[idx];
        else
            list[pidx]->right = list[idx];
        return list[pidx]->val;
    }
    TreeNode* get_root() { return root; }
};

题解 2 - rust

• 编辑时间：2022-07-25
• 内存消耗：2.5MB
• 编程语言：rust
• 解法介绍：利用完全二叉树特性，列表快速查找父亲。

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
struct CBTInserter {
    root: Rc<RefCell<TreeNode>>,
    list: RefCell<Vec<Rc<RefCell<TreeNode>>>>,
}
impl CBTInserter {
    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        let root = root.unwrap();
        let list: RefCell<Vec<Rc<RefCell<TreeNode>>>> = RefCell::new(Vec::new());
        {
            let mut list = list.borrow_mut();
            let mut q: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
            q.push_back(root.clone());
            list.push(root.clone());
            while q.len() > 0 {
                let node = q.pop_front().unwrap();
                if node.as_ref().borrow().left.is_some() {
                    q.push_back(node.as_ref().borrow().left.as_ref().unwrap().clone());
                    list
                        .push(node.as_ref().borrow().left.as_ref().unwrap().clone());
                }
                if node.as_ref().borrow().right.is_some() {
                    q.push_back(node.as_ref().borrow().right.as_ref().unwrap().clone());
                    list
                        .push(node.as_ref().borrow().right.as_ref().unwrap().clone());
                }
            }
        }
        Self { root, list }
    }
    fn insert(&self, val: i32) -> i32 {
        let mut list = self.list.borrow_mut();
        let idx = list.len();
        let pidx = if idx & 1 == 1 { idx / 2 } else { idx / 2 - 1 };
        let node = Rc::new(RefCell::new(TreeNode::new(val)));
        list.push(node.clone());
        let mut parent = list.get(pidx).unwrap().as_ref().borrow_mut();
        if idx & 1 == 1 {
            parent.left = Some(node.clone());
        } else {
            parent.right = Some(node.clone());
        }
        parent.val
    }
    fn get_root(&self) -> Option<Rc<RefCell<TreeNode>>> {
        Some(self.root.clone())
    }
}