623.在二叉树中增加一行

链接：623.在二叉树中增加一行
难度：Medium
标签：树、深度优先搜索、广度优先搜索、二叉树
简介：给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。

题解 1 - rust

• 编辑时间：2022-08-05
• 内存消耗：2.6MB
• 编程语言：rust
• 解法介绍：层序遍历。

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn add_one_row(
        root: Option<Rc<RefCell<TreeNode>>>,
        val: i32,
        depth: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if depth == 1 {
            let mut new_root = TreeNode::new(val);
            new_root.left = root;
            Some(Rc::new(RefCell::new(new_root)))
        } else {
            let root = root.unwrap();
            let mut q = VecDeque::<Rc<RefCell<TreeNode>>>::new();
            q.push_back(root.clone());
            let (mut size, mut level) = (1, 1);
            while level < depth - 1 {
                let node = q.pop_front();
                let node = node.as_ref().unwrap().borrow();
                if node.left.is_some() {
                    q.push_back(node.left.as_ref().unwrap().clone());
                }
                if node.right.is_some() {
                    q.push_back(node.right.as_ref().unwrap().clone());
                }
                size -= 1;
                if size == 0 {
                    level += 1;
                    size = q.len();
                }
            }
            while !q.is_empty() {
                let node = q.pop_front();
                let mut node = node.as_ref().unwrap().borrow_mut();
                let left = node.left.clone();
                let mut new_left = TreeNode::new(val);
                new_left.left = left;
                node.left = Some(Rc::new(RefCell::new(new_left)));
                let right = node.right.clone();
                let mut new_right = TreeNode::new(val);
                new_right.right = right;
                node.right = Some(Rc::new(RefCell::new(new_right)));
            }
            Some(root)
        }
    }
}

题解 2 - cpp

• 编辑时间：2022-08-05
• 执行用时：20ms
• 内存消耗：24.4MB
• 编程语言：cpp
• 解法介绍：排序后，从后往前取值。

class Solution {
   public:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        if (depth == 1) return new TreeNode(val, root, nullptr);
        queue<TreeNode*> q;
        q.push(root);
        int size = 1, level = 1;
        while (level < depth - 1) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            if (--size == 0) {
                level++;
                size = q.size();
            }
        }
        while (q.size()) {
            TreeNode* node = q.front();
            q.pop();
            node->left = new TreeNode(val, node->left, nullptr);
            node->right = new TreeNode(val, nullptr, node->right);
        }
        return root;
    }
};