114.Flatten-Binary-Tree-to-Linked-List

114. Flatten Binary Tree to Linked List

题目地址

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

代码

Approach #1 Recursion

Time Complexity && Space Complexity: O(N)

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Approach #1 Recursion

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

Approach #2 Iteration

class Solution {
  public void flatten(TreeNode root) {
        helper(root);
  }

  public TreeNode helper(TreeNode node) {
    if (node == null)        return null;

    if (node.left == null && node.right == null) {
      return node;
    }

    TreeNode leftTail = helper(node.left);
    TreeNode rightTail = helper(node.right);

    if (leftTail != null) {
      leftTail.right = node.right;
      node.right = node.left;
      node.left = null;
    }

    return rightTail == null ? leftTail : rightTail;
  }
}

Approach #3 O(1) Iteration

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

    TreeNode node = root;

    while (node != null) {
      if (node.left != null) {
        TreeNode rightmost = node.left;
        while (rightmost.right != null) {
          rightmost = rightmost.right;
        }

        rightmost.right = node.right;
        node.right = node.left;
        node.left = null;
      } /* end if node.left != null */

      node = node.right;
    }
  }
}

Approach #2 Iterative + Stack

Time Complexity & Space Complexity: O(N)

class Solution {
  public void flatten(TreeNode root) {
    if (root == null)        return;
    int START = 1, END = 2;

    TreeNode tailNode = null;
    Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>();
    stack.push(new Pair<TreeNode, Integer>(root, START));

    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> nodeData = stack.pop();
      TreeNode currentNode = nodeData.getKey();
      int recursionState = nodeData.getValue();

      if (currentNode.left == null && currentNode.right == null) {
        tailNode = currentNode;
        continue;
      }

      if (recursionState = START) {
        if (currentNode.left != null) {
          stack.push(new Pair<TreeNode, Integer>(currentNode, END));
          stack.push(new Pair<TreeNode, Integer>(currentNode.left, START));
        } else if (currentNode.right != null) {
          stack.push(new Pair<TreeNode, Integer>(currentNode.right, START));
        }
      } else {
        TreeNode rightNode = currentNode.right;
        if (tailNode != null) {
          tailNode.right = currentNode.right;
          currentNode.right = currentNode.left;
          currentNode.left = null;
          rightNode = tailNode.right;
        }

        if (rightNode != null) {
          stack.push(new Pair<TreeNode, Integer>(rightNode, START));
        }
      }
    }
  }
}