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


  • 2
    M
    /*
        把pre-order遍历到的节点按顺序接起来即可.
        要求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
    M

    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
    M

    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
    J

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