[LeetCode] 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

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

問題描述：給定一個二叉樹，將它變成一個類似上面那樣的鏈表，而且操作要原地進行。
根據上面兩個樹的樣子，可以看到，在鏈表形式中，節點的左孩子為空，右孩子為先序遍歷中當前節點的前一個節點。
因此，可以構造這樣一個函數，它將以root為根的樹變成上面這樣類似鏈表的形式，返回整個子樹的先序遍歷的最後一個節點。
那麼，它如何實現這個過程呢？對它的左子樹調用上面的函數，將左邊變成類似鏈表的形式，並且獲得了左子樹中先序遍歷的最後一個節點last_node，接著，將最後一個幾點的
左孩子置空，右孩子置為root->right，然後root->right = root->left，最後，如果root->right不空，則對右子樹調用上面的函數，並返回右子樹的最後一個節點。
在這裡還有一種特殊情況，就是左右子樹都為空，此時，不做任何操作，然後返回該節點本身。
#include 
#include 
#include 
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void tree_insert(TreeNode *&root, TreeNode *pnode)
{
    if(root == NULL) {
        root = pnode;
        return;
    }
    if(pnode->val <= root->val) {
        tree_insert(root->left, pnode);
    }
    else {
        tree_insert(root->right, pnode);
    }
}

void tree_create(TreeNode *&root, vector::iterator beg, vector::iterator end)
{
    TreeNode *pnode = NULL;
    while(beg != end) {
        pnode = new TreeNode(*beg);
        tree_insert(root, pnode);
        ++beg;
    }
}

void tree_traverse(TreeNode *root)
{
    if(root != NULL) {
        cout << root->val << " ";
        tree_traverse(root->left);
        tree_traverse(root->right);
    }
}

void tree_structure(TreeNode *root)
{
    if(root != NULL) {
        cout << "root :" << root->val << endl;
        if(root->left == NULL) {
            cout << "left child is NULL " << endl;
            tree_structure(root->right);
        }
        else
            cout << "error!" << endl;
    }
}

void tree_destroy(TreeNode *&root)
{
    if(root != NULL) {
        tree_destroy(root->left);
        tree_destroy(root->right);
        delete root;
    }
}

class Solution {
public:
    TreeNode *flatten_child(TreeNode *root)
    {
        if(root != NULL) {
            if(root->left == NULL && root->right == NULL)
                return root;
            TreeNode *last_node = NULL;
            if(root->left == NULL) {
                return flatten_child(root->right);
            }
            last_node = flatten_child(root->left);
            if(root->right == NULL) {
                root->right = root->left;
                root->left = NULL;
                return last_node;
            }
            last_node->right = root->right;
            last_node->left = NULL;
            root->right = root->left;
            root->left = NULL;
            return flatten_child(last_node->right);
        }
    }

    void flatten(TreeNode *root)
    {
        if(root != NULL)
            flatten_child(root);
    }
};

int main(int argc, char *argv[])
{
    int arr[] = {3, 2, 1, 4, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    vector vec(arr, arr + len);
    TreeNode *tree = NULL;
    tree_create(tree, vec.begin(), vec.end());
    tree_traverse(tree);
    cout << endl;
    Solution sol;
    sol.flatten(tree);
    tree_structure(tree);
    tree_destroy(tree);

    return 0;
}

為了展示樹的構造和變化，給出了整個程序。首先構造了一個二叉樹，然後對它進行了變換，最後用tree_structure()打印樹的結構情況。