Share my 7-line O(1)-space java code with explanations

  • 2
        要求in-place... pre-order就是先处理根, 再处理左子树, 再处理右子树.
        -- 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;

  • 0

    Nice solution, but not everybody in the world is Chinese (although you guys might think so...) Can you modify your comments so everybody understands?

  • 0

    Sorry for that :( The reason it originally posted in Chinese is that my English is not good, but how can it be good if I don't practice it?

  • 0

    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 pre-order 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 bottom-right of the left subtree.

  • 0

    Thank you! You can see that if you spend some additional time, you can explain in common English what you explain in Chinese.

  • 0

    @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]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.