在二叉树插入中，只有左树是右树。正确的树是错误的

Question

我有一个btree类和一个insert函数，可以将节点插入到树中。但是树没有在右边插入节点。你知道吗

我正在创建根节点。insert函数将左、右节点正确地插入到根节点。你知道吗

然后递归地，我尝试在左侧节点插入两个节点，在右侧节点插入两个节点。但在这一步中，所有节点只添加到左侧。节点也被添加到无父节点。你知道吗

我知道，我在insert函数的最后一个else语句中犯了一个错误。但我试过很多组合，但都有一些错误。你知道吗

class BinTree(object):
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

  def insert(self,val):
    if self.left is None:
      self.left = BinTree(val)
    elif self.right is None:
      self.right = BinTree(val)
    elif self.left:
      self.left.insert(val)
    else:
      self.right.insert(val)

root = BTree('A')
root.insert('B')
root.insert('C')
root.insert(None)
root.insert('D')
root.insert(None)
root.insert('E')
root.insert('F')

Expected:
                 A
              /     \
             B       C
            /\       /\
        None  D  None  E
             /
            F

Getting:
                 A
              /     \
             B       C
            / \
        None   D
         /  \
     None    E
       /
      F

Answer 1

对于保存的当前字段，使用递归无法真正得到所需的结果。每个节点只“知道”其当前状态，这就是为什么树的右侧将永远保持在深度1。你知道吗

我们想到的一个解决方案是添加right children和left children数量字段。这将有助于跟踪余额。它看起来是这样的：

 class Node(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.right_count = 0
        self.left_count = 0
        self.even_depth = True
        self.needed_to_even = 1

    def insert(self, val):
        if self.left is None:
            self.left = Node(val)
            self.left_count += 1
        elif self.right is None:
            self.right = Node(val)
            self.right_count += 1
        elif self.left_count > self.right_count + self.needed_to_even or not self.even_depth:
            self.even_depth = False
            if self.left_count == self.right_count:
                self.needed_to_even *= 2
                self.even_depth = True
            self.right.insert(val)
            self.right_count += 1
        else:
            self.left.insert(val)
            self.left_count += 1