当您必须在末尾添加节点（二叉树构造）时，如何继续移动根？

Question

这不是一个家庭作业问题。我正在练习面试。这是问题描述

编写一个方法构造，它接受一个整数n作为参数，并构造一个新的整数树，其中n个节点编号为0到（n-1），这样树的有序遍历将按顺序产生值。树应该是平衡的，因为任何节点的左子树中的值数量应该总是在其右子树中的值数量之一之内。如果节点的两个子树中的一个有额外的值，它应该出现在正确的子树中。

例如，给定IntTree类型的变量树，调用tree。构造（7）；应生成如下所示的第一棵树。如果电话是在树上。构造（10）；，树的状态应该是下面显示的第二棵树的状态。

假设您正在将此方法添加到IntTree类，定义如下：

公共类IntTree{private IntTreeNode overallRoot；…}

以下是我的初步想法空的情况很容易，你只需使节点为空。我看到，对于任何n，都需要引入一个值为n-1的新节点。我还看到，对于所有的奇数ns，总的根向上移动了1。我一开始就通过移动整棵树来解决这个问题。（即将原始根向左移动，将新根移动到整个根）。要做到这一点，您需要不断访问整个根目录。问题是，当我达到n=4时，我必须在整个节点的子节点右侧引入一个新节点3（意味着我无法访问整个节点）。是否有更好的方法（添加和维护访问权限）？

Answer 1

为确保满足以下条件：

如果一个节点的两个子树中有一个额外的值，它应该出现在右子树中。

这应该行得通。

Node make (int a, int b) {
    if (a > b) return null;
    if (a == b) return new Node (a);
    int r = a + ((b - a) >>> 1);
    return new Node (r, make(a, r-1), make(r+1, b));
}

Answer 2

有几种方法，但在面试中最简单的方法是递归。对于范围[a， b]将其分为[a， r-1]， r，[r 1， b]。然后构建一个以r为根的树，并递归地为范围构建树，使它们的根成为子元素。剩下的就是确保失踪儿童的条件得到满足。这只是仔细挑选r。

class InorderIntegerTree {

  Node root;

  static class Node {

    int val;
    Node left, right;

    Node(val, left, right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }

  Node make(int a, int b) {
    if (a > b) return null;
    int r = b + (b - a) / 2;
    return new Node(r, make(a, r-1), make(r+1, b));
  }

  InorderIntegerTree(int n) {
    root = make(0, n-1);
  }  
}