114. Flatten Binary Tree to Linked List

Difficulty:
Related Topics:
Similar Questions:

    Problem

    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
    

    Solution

    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {void} Do not return anything, modify root in-place instead.
     */
    var flatten = function (root) {
      helper(root);
    };
    
    var helper = function (root) {
      if (!root) return null;
    
      var leftLast = helper(root.left);
      var rightLast = helper(root.right);
    
      if (root.left) {
        leftLast.right = root.right;
        root.right = root.left;
      }
    
      root.left = null;
    
      return rightLast || leftLast || root;
    };
    

    Explain:

    nope.

    Complexity: