114. Flatten Binary Tree to Linked List (Medium)

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Solutions

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        recurse(root);
    }

    private TreeNode recurse(TreeNode root) {
        // return null if reach the end
        if (root == null) {
            return null;
        }

        // flatten left branch
        TreeNode left = recurse(root.left);

        // flatten right branch
        TreeNode right = recurse(root.right);

        // FIXME Do not forget to unlink to root.left
        root.left = null;

        if (left != null) {
            // append right branch to the end of left branch if left exists
            append(left, right);

            // link root.right to the head of left branch if left exits.
            // if left not exists, do not modify anything.
            root.right = left;
        }

        return root;
    }


    private void append(TreeNode left, TreeNode right) {
        while (left.right != null) {
            left = left.right;
        }

        left.right = right;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""