/*
把preorder遍历到的节点按顺序接起来即可.
要求inplace... preorder就是先处理根, 再处理左子树, 再处理右子树.
所以只要
 root.left接在root.right的位置上
 原先的root.right接在left subtree的"最右边"
*/
public class Solution {
public void flatten(TreeNode root) {
for (; root!=null; root=root.right) {
if (root.left == null) { continue; }
TreeNode p = root.left; // p != null guaranteed
while (p.right != null) { p = p.right; }
p.right = root.right;
root.right = root.left;
root.left = null;
}
}
}
Share my 7line O(1)space java code with explanations


It can be seen that, when you traverse the output linked list, you will get a sequence whose order is identical with that when you preorder traverse the input binary tree, that is, root > left subtree > right subtree. Therefore, for each treenode (current root), do the following: 1. Make the root of left subtree its right child; 2. Since right subtree should be processed after the left subtree, so right subtree should be concatenated to the bottomright of the left subtree.

@agave The translation is : in each iteration, move the curr root's [right tree] under the most right node of curr root's [left tree]