LeetCode 114 - Flatten Binary Tree to Linked List

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

         1
        / \
       2   5
      / \   \
     3   4   6

 
The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Solution 1:
Pre-orderシーケンス遍歴.前回アクセスしたノードをprevノードで保存し、左の子供と右の子供を更新します.

private TreeNode prev = null;
public void flatten(TreeNode root) {
    if(root == null) return;
    TreeNode right = root.right; //      ，     flatten         
    if(prev != null) {
        prev.left = null; //           ，        ，       
        prev.right = root; //      ，        ，         ，   
    }
    prev = root;
    flatten(root.left);
    flatten(right); //  ，       root.right,    StackOverFlow
}

 
Solution 2:
再帰的でないやり方.

public void flatten(TreeNode root) {
    TreeNode node = root;
    while(node != null) {
        if(node.left != null) {
            TreeNode rightLeaf = node.left;
            while(rightLeaf.right != null) {
                rightLeaf = rightLeaf.right;
            }
            rightLeaf.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        node = node.right;
    }
}

 
Solution 3:
非再帰はスタックで処理される.

public void flatten(TreeNode root) {
    if(root == null) return;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    TreeNode leaf = root;
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if(node.right != null) stack.push(node.right);
        if(node.left != null) stack.push(node.left);
        if(leaf != node) {
            leaf.left = null;
            leaf.right = node;
            leaf = node;
        }
    }
}