1 class Solution { 2 public: 3     void flatten(TreeNode* root) { 4         if(!root) return; 5         flatten(root->left); 6         flatten(root->right); 7          8         TreeNode* right = root->right; 9         root->right = root->left;10         root->left = NULL;11         while(root->right){12             root = root->right;13         }14         root->left = NULL;15         root->right = right;16     }17 };

原本以为最后flatten的树必须是按顺序按小到大的，这样一来

          3

   1            4

2     5

这棵树左右子树flatten后左边是1-2-5，右边是4，4还要插入左子树。后来发现想多了，只需要所有节点均无左子树即可，但是还是要按照一定顺序的。

题意仍不失很明确，留坑。

题目要求的顺序是前序，即root - root->left - root->right。

将上面这棵树输入：

Your input

[3,1,4,2,5]

Your answer

[3,null,1,null,2,null,5,null,4]

Expected answer

[3,null,1,null,2,null,5,null,4]   即确实是前序。 还有其他算法，未看，留坑。