LeetCode問題解(51):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

问题解:自分で作った愚かな方法は、スタックで前顺に遍歴します.
C++版:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        if(!root)
            return;
        if(!root->left && !root->right)
            return;
        
        stack<TreeNode*> unvisited;
        unvisited.push(root);
        while(unvisited.size()) {
            TreeNode* current = unvisited.top();
            unvisited.pop();
            if(current->right) {
                unvisited.push(current->right);
                if(current->left) {
                    unvisited.push(current->left);
                    current->right = current->left;
                    current->left = NULL;
                } 
            } else {
                if(current->left) {
                    unvisited.push(current->left);
                    current->right = current->left;
                    current->left = NULL;
                } else {
                    if(unvisited.size())
                        current->right = unvisited.top();
                    else
                        current->right = NULL;
                }
            }
        }
    }
};

ネットは空間の複雑さO(1)アルゴリズムを学んで、本当のin-place flattern.Morris Algorithm for binary tree traversalと呼ばれているようです.
Java版:

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

Python版:

class Solution:
    # @param root, a tree node
    # @return nothing, do it in place
    def flatten(self, root):
        if root == None:
            return
        current = root
        while current != None:
            if current.left != None:
                next = current.left
                while next.right != None:
                    next = next.right
                next.right = current.right
                current.right = current.left
                current.left = None
            current = current.right