leetcode 114. 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

要求空间复杂度为O(1)

可以看到最后的结果应为先序遍历的顺序

对一棵树，作如下约定：
尾： 树先序遍历的最后一个结点，一般是右下角的结点
头： 树先序遍历的第一个结点， 也就是头结点
同样，对于左右子树，可以定义左头（leftHead）、左尾（LeftRear）、右头（rightHead）、右尾（rightRear）

我所写的为一个递归函数，返回值为尾结点

大体流程：

• 1 定位左尾
• 2 存储右头
• 3 如果存在左尾，则左尾的right值赋为右头
• 4 left值赋成NULL
• 5 如果存在右尾则返回右尾 否则返回左尾

class Solution {
public:
    void flatten(TreeNode* root) {
        flattenTree(root);
    }
    TreeNode* flattenTree(TreeNode* root)
    {
        if(!root)
            return NULL;
        if(!root->left && !root->right)
            return root;
        TreeNode* rightHead = root->right;
        TreeNode* leftRear = flattenTree(root->left);
        TreeNode* rightRear = flattenTree(root->right);
        if(root->left)
        {
            root->right = root->left;
            root->left = NULL;
            leftRear->right = rightHead;
        }
            if(rightRear)
            return rightRear;
        else
            return leftRear;
    }
};

时间复杂度 O(N)
空间复杂度 O(1)