使用栈构造二叉树代码异常：节点7缺失左子节点该如何修复？

现象判断 #

你观测到的节点7无左子节点的现象不正常，按照你给出的构造逻辑，正确生成的树中节点7的左子节点应为4。

问题原因 #

你在addNode函数中给新节点赋值左子节点的逻辑存在错误，多余的if stack[-1].rightChild is None判断导致只有栈顶节点原本没有右子节点时，才会给新节点设置左子节点。
而你要实现的笛卡尔树构造逻辑要求：新节点挂到栈顶节点的右子节点位置时，必须把栈顶节点原有的右子树整体作为新节点的左子树，该操作不受栈顶原有右子节点是否为空的限制。

修复方案 #

只需要去掉addNode函数里多余的if判断即可，修改后的addNode代码如下：

def addNode(x, stack, root):
    while len(stack) != 0 and stack[-1].value < x:
        stack.pop()
    
    node = Node(x)
    if len(stack) == 0:
        node.leftChild = root
        root = node
    else:
        # 去掉多余的if判断，直接给新节点左子节点赋值为栈顶的原有右子节点
        node.leftChild = stack[-1].rightChild
        stack[-1].rightChild = node
    stack.append(node)
    return root, stack

修改后运行代码，生成的树结构将和预期一致：节点7的左子节点为4，右子节点为6。

内容的提问来源于stack exchange，提问作者Patrick