[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()打印树的结构情况。