装饰树

此题的核心思路是在原二叉树的每个节点与其子节点之间插入一个值为-1的新节点。递归方法是用来遍历每个节点，并在遍历过程中插入新节点。如果当前节点有左子节点，则在当前节点的左子节点前插入一个值为-1的新节点，并将原左子节点变为新插入节点的左子节点。同样的处理适用于右子节点。递归继续对新插入的（值为-1的）节点的左或右子节点（视原始子节点位置而定）调用同样的过程，直到所有的子节点都被处理完毕。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 Solution:
    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root==None: return None # 若根为空，直接返回None
        # 叶节点直接返回，因为无需在其与子节点之间插入新节点
        if root.left==None and root.right==None: return root
        if root.left!=None: # 处理左子树
            node=TreeNode(-1) # 创建新节点
            node.left=root.left # 将新节点的左子节点设为原左子节点
            root.left=node # 将原根节点的左子节点更新为新节点
            node.right=None # 新节点的右子节点为空
            self.expandBinaryTree(node.left) # 递归处理新的左子节点
        if root.right!=None: # 处理右子树
            node=TreeNode(-1) # 创建新节点
            node.right=root.right # 将新节点的右子节点设为原右子节点
            root.right=node # 将原根节点的右子节点更新为新节点
            node.left=None # 新节点的左子节点为空
            self.expandBinaryTree(node.right) # 递归处理新的右子节点
        return root