2025/8/10

题目（Medium)：

---

我的思路：

1.左子树直接塞入法

观察树展开前后可以发现：

①树的展开后顺序为前序遍历节点顺序

②树展开后所有节点的左孩子都为None

因此，如果要原地对它进行展开的话就要想一想这些消失的左孩子都去哪里？是不是都按某种顺序连接到其他节点的右孩子上去了呀，那这个节点要是本来就有右孩子那怎么办呢？那我们直接把这个右孩子先摘下来，等把左孩子移接到这上面之后，再把右孩子连接到新连接的右子树的最右侧节点就好了。

所以步骤就是：

①先让一个指针指向根节点位置

②如果指针所指节点存在左子树，那就先找到这个左子树最右侧的节点（比如上图中第一轮是4）

③然后把左子树插入到指针所指节点的右指针，左子树最右侧节点的右指针连接老的右子树

④让指针往右孩子移动，若指针不为空则重复步骤二三。

具体代码如下：

# 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 flatten(self, root: Optional[TreeNode]) -> None:
        #左子树直接塞入
        if not root:
            return None
        
        p = root
        while p:
            if p.left:
                #如果它的左子树存在，那就先找到左子树最右边的节点
                maxRightNode = self.findMaxRightNode(p.left)
                
                #然后把左子树的根节点连接到根节点的右孩子上
                oldRight = p.right
                p.right = p.left
                p.left = None
                maxRightNode.right = oldRight

            #一直让P往右孩子移动
            p = p.right
        
    def findMaxRightNode(self, root: Optional[TreeNode]):
        if not root:
            return None
        
        p = root
        while p.right:
            p = p.right
        
        return p

时间复杂度：O（N）

空间复杂度：O（1）

2.前序遍历+列表记录以重构

其实还有一种很容易就可以想得到的方法，既然已经知道它是前序遍历的顺序展开的了，那我们先对这颗树进行前序遍历并把遍历的节点放在一个列表中。然后再在这个列表的基础上去展开树即可。

这里我们前序遍历可以用递归或者迭代的方式实现，递归的方式比较简单，我们这里用迭代的形式来实现。迭代的前序遍历需要用一个栈来辅助

具体步骤如下：

①先声明一个遍历列表和一个栈，并让一个指针指向根节点位置

②只要指针不为空就循环进行如下操作：把当前位置节点加入列表中，把当前位置节点加入栈中，指针往左孩子移动

③弹出栈中节点，然指针移动到这个节点的右孩子处

④只要指针或者栈不为空就一直重复步骤二三

⑤到这一步已经获得前序遍历顺序排列的节点，然后我们只要列表迭代访问以进行连接操作即可

具体代码如下：

# 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 flatten(self, root: Optional[TreeNode]) -> None:
       #迭代前序遍历 + 列表记录展开
        stack,resList = list(), list()
        p = root

        while p or stack:
            while p:
                #访问根节点
                resList.append(p)
                stack.append(p)
                #访问左子树
                p = p.left
            #访问右子树
            p = stack.pop()
            p = p.right
        
        for i in range(1, len(resList)):
            pre,cur = resList[i-1], resList[i]
            pre.left = None
            pre.right = cur
        

时间复杂度：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 flatten(self, root: Optional[TreeNode]) -> None:
        #找到前驱节点
        if not root:
            return None
        
        p = root
        while p:
            if p.left:
                nxt = pre = p.left
                #获取该右子树的最右侧节点
                while pre.right:
                    pre = pre.right
                #直接把根节点的右子树接在这个节点右孩子处
                pre.right = p.right
                #然后再把这个左子树移动到根节点右孩子处
                p.left = None
                p.right = nxt
            
            #把指针往右孩子移动
            p = p.right

时间复杂度：O（N）

空间复杂度：O（1）

---

总结：

①对于要原地对树进行操作的时候，就要尽可能地想这颗树左右孩子之间的联系。并尽可能地利用上面的节点进行存储操作

②对于树的前序遍历的实现，可以用递归或者迭代，迭代用一个栈来辅助，主要是用于当遍历完根节点，左子树之后，可以立刻前往根节点的右子树