📃 题目描述

题目链接：

• 剑指 Offer II 043. 往完全二叉树添加节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 完全二叉树插入器 - 完全二叉树插入器 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

参数传进来的 root 就已经是完全二叉树了

我们只需要插入一个节点就行

很简单，直接用 list 存储完全二叉树的结果，插入节点直接放在 lsit 的最后面就行了。

新插入节点的父节点也很好算，根据下标来做：TreeNode parent = list.get(list.size() / 2 - 1);

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class CBTInserter {

    private List<TreeNode> list;

    // root 是个完全二叉树
    // 层次遍历将结果存入 list
    public CBTInserter(TreeNode root) {
        this.list = new ArrayList<>();
    
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < queue.size(); i ++) {
                TreeNode cur = queue.poll();
                list.add(cur);

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }
    
    public int insert(int v) {
        TreeNode newNode = new TreeNode(v);
        list.add(newNode);

        // newNode 的父节点
        TreeNode parent = list.get(list.size() / 2 - 1);

        // newNode 是左孩子
        if (list.size() % 2 == 0) {
            parent.left = newNode;
        }
        // newNode 是右孩子
        else {
            parent.right = newNode;
        }

        return parent.val;
    }
    
    public TreeNode get_root() {
        return list.isEmpty() ? null : list.get(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();
 */

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：