Java answer, flip the tree, and then create a right lean preorder linked list


  • 0
    S

    it is easy to get a preorder left lean linked list by recursively flatten the left tree, and then flatten right tree, and attach the right tree at the end of the left tree...
    In order to get a right lean preorder linked list, we can first flip the left and right subtree, and then create the right lean structure similar as previous method...

    class Solution {
        public void flatten(TreeNode root) {
            if (root == null) return;
            if (root.left == null && root.right == null) return;
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            flatten(root.left);
            flatten(root.right);
            TreeNode node = root;
            while (node.right != null) {
                node = node.right;
            }
            node.right = root.left;
            root.left = null;  
        }    
    }
    

Log in to reply
 

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