Question

剑指 Offer II 043. 往完全二叉树添加节点

题目描述

完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

• CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
• CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
• CBTInserter.get_root() 将返回树的根节点。

 

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]

示例 2：

输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]

 

提示：

• 最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
• 每个测试用例最多调用 CBTInserter.insert  操作 10000 次。
• 给定节点或插入节点的每个值都在 0 到 5000 之间。

 

注意：本题与主站 919 题相同： https://leetcode.cn/problems/complete-binary-tree-inserter/

解法

方法一

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class CBTInserter:
  def __init__(self, root: TreeNode):
    self.tree = []
    q = deque([root])
    while q:
      for _ in range(len(q)):
        node = q.popleft()
        self.tree.append(node)
        if node.left:
          q.append(node.left)
        if node.right:
          q.append(node.right)

  def insert(self, v: int) -> int:
    pid = (len(self.tree) - 1) >> 1
    node = TreeNode(v)
    self.tree.append(node)
    p = self.tree[pid]
    if p.left is None:
      p.left = node
    else:
      p.right = node
    return p.val

  def get_root(self) -> TreeNode:
    return self.tree[0]


# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()

/**
 * 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> tree;

  public CBTInserter(TreeNode root) {
    tree = new ArrayList<>();
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
      TreeNode node = q.pollFirst();
      tree.add(node);
      if (node.left != null) {
        q.offer(node.left);
      }
      if (node.right != null) {
        q.offer(node.right);
      }
    }
  }

  public int insert(int v) {
    int pid = (tree.size() - 1) >> 1;
    TreeNode node = new TreeNode(v);
    tree.add(node);
    TreeNode p = tree.get(pid);
    if (p.left == null) {
      p.left = node;
    } else {
      p.right = node;
    }
    return p.val;
  }

  public TreeNode get_root() {
    return tree.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();
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class CBTInserter {
public:
  vector<TreeNode*> tree;

  CBTInserter(TreeNode* root) {
    queue<TreeNode*> q{{root}};
    while (!q.empty()) {
      auto node = q.front();
      q.pop();
      tree.push_back(node);
      if (node->left) q.push(node->left);
      if (node->right) q.push(node->right);
    }
  }

  int insert(int v) {
    int pid = tree.size() - 1 >> 1;
    TreeNode* node = new TreeNode(v);
    tree.push_back(node);
    TreeNode* p = tree[pid];
    if (!p->left)
      p->left = node;
    else
      p->right = node;
    return p->val;
  }

  TreeNode* get_root() {
    return tree[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();
 */

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
type CBTInserter struct {
  tree []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
  q := []*TreeNode{root}
  tree := []*TreeNode{}
  for len(q) > 0 {
    node := q[0]
    tree = append(tree, node)
    q = q[1:]
    if node.Left != nil {
      q = append(q, node.Left)
    }
    if node.Right != nil {
      q = append(q, node.Right)
    }
  }
  return CBTInserter{tree}
}

func (this *CBTInserter) Insert(v int) int {
  pid := (len(this.tree) - 1) >> 1
  node := &TreeNode{Val: v}
  this.tree = append(this.tree, node)
  p := this.tree[pid]
  if p.Left == nil {
    p.Left = node
  } else {
    p.Right = node
  }
  return p.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
  return this.tree[0]
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Insert(v);
 * param_2 := obj.Get_root();
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.left = (left===undefined ? null : left)
 *   this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 */
var CBTInserter = function (root) {
  this.tree = [];
  const q = [root];
  while (q.length) {
    const node = q.shift();
    this.tree.push(node);
    if (node.left) {
      q.push(node.left);
    }
    if (node.right) {
      q.push(node.right);
    }
  }
};

/**
 * @param {number} v
 * @return {number}
 */
CBTInserter.prototype.insert = function (v) {
  const pid = (this.tree.length - 1) >> 1;
  const node = new TreeNode(v);
  this.tree.push(node);
  const p = this.tree[pid];
  if (!p.left) {
    p.left = node;
  } else {
    p.right = node;
  }
  return p.val;
};

/**
 * @return {TreeNode}
 */
CBTInserter.prototype.get_root = function () {
  return this.tree[0];
};

/**
 * Your CBTInserter object will be instantiated and called as such:
 * var obj = new CBTInserter(root)
 * var param_1 = obj.insert(v)
 * var param_2 = obj.get_root()
 */