leetcode114

class Solution {
public:
    void flatten(TreeNode* root) {
        while(root){
            if(root->left){
                TreeNode* pre=root->left;
                while(pre->right){
                    pre=pre->right;
                    
                }
                pre->right=root->right;
                root->right=root->left;
                root->left=nullptr;
            }
            root=root->right;
        }
    }
};

补充一个DFS遍历，然后倒叙组装成类似链表的解决方案，使用python实现：

class Solution:    
    def preOrder(self,root,l):
        if root != None:
            l.append(root)

            self.preOrder(root.left,l)
            self.preOrder(root.right,l)

    def flatten(self, root: 'TreeNode') -> 'None':
        if root == None:
            return
        l = list()
        self.preOrder(root,l)
        root = l[len(l)-1]
        for i in range(len(l)-2,-1,-1):
            l[i].left = None
            l[i].right = root
            root = l[i]

python的递归实现：

 1 class Solution:
 2     def build(self,root):
 3         if root != None:
 4             if root.left != None and root.right != None:
 5                 right = self.build(root.right)#重建右子树
 6                 left = self.build(root.left)#重建左子树
 7                 leaf = left
 8                 while leaf.right != None:#找到左子树的叶子节点
 9                     leaf = leaf.right
10                 leaf.right = right#右子树连接到左子树的末尾
11                 root.right = left#根节点修改右子树
12                 root.left = None#根结点左子树设为空
13                 return root
14             elif root.left != None and root.right == None:
15                 root.right = self.build(root.left)
16                 root.left = None
17                 return root
18             elif root.left == None and root.right != None:
19                 root.right = self.build(root.right)
20                 return root
21             else:
22                 return root
23         return None
24     
25     def flatten(self, root: TreeNode) -> None:
26         """
27         Do not return anything, modify root in-place instead.
28         """
29         self.build(root)