[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

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

解法1：preorder traversal

从题目的例子马上发现其实就是preorder transverse整个tree，然后根据这个访问顺序，后访问到的节点成为先访问到的节点的右子节点。那么最不动脑的方法就是preorder transverse的时候把整个节点序列保存在一个vector中。最后再依次连起来。这个解法的空间复杂度包括了递归深度O(log n)和vector的空间O(n)，所以总的空间复杂度是O(n)。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: void flatten(TreeNode *root) { if(!root) return; vector<TreeNode*> allNodes; preorder(root, allNodes); int n = allNodes.size(); for(int i=0; i<n-1; i++) { allNodes[i]->left = NULL; allNodes[i]->right = allNodes[i+1]; } allNodes[n-1]->left = allNodes[n-1]->right = NULL; } void preorder(TreeNode *root, vector<TreeNode*> &allNodes) { if(!root) return; allNodes.push_back(root); preorder(root->left, allNodes); preorder(root->right, allNodes); } };

解法2：递归构建

假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：

    1
  /    \
 2     5
  \       \
   3      6 <- rightTail
     \
      4  <- leftTail

如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：

temp = root->right
root->right  = root->left
root->left = NULL
leftTail->right = temp

这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: void flatten(TreeNode *root) { TreeNode* rightTail = flattenBT(root); } TreeNode* flattenBT(TreeNode* root) { if(!root) return NULL; TreeNode *leftTail = flattenBT(root->left); TreeNode *rightTail = flattenBT(root->right); if(root->left) { TreeNode *temp = root->right; root->right = root->left; root->left = NULL; leftTail->right = temp; } if(rightTail) return rightTail; if(leftTail) return leftTail; return root; } };

需注意几个细节
ln 11：只有当左子树存在时才将它插入右子树中
ln 18-20：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。