Leetcode | Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

整体思路如下：

1. 整体还是前序遍历。遍历完一颗子树之后，返回最后的节点。

2. next指针初始化为root；

2. 如果左子树不为空。那么把root->right 指向root->left再递归；并设置next指针为左子树的返回值，也就是左子树的最后一个元素。

3. 如果右子树不为空，那么把next->right指向右子树的根结点，最终返回右子树的最后一个结点；

4. 如果右子树为空，那么返回的应该就是左子树的最后一个结点，也就是next；

5. 每次遍历到一个结点，都必须设置它的左结点为NULL，不然会报runtime error.

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     void flatten(TreeNode *root) {
13         recursive(root);
14     }
15     
16     TreeNode* recursive(TreeNode *root) {
17         if (root == NULL) return NULL;
18         
19         TreeNode *left = root->left, *right = root->right, *next = root;
20         root->left = NULL;
21         if (left != NULL) {
22             root->right = left;
23             next = recursive(left);
24         }
25         if (right == NULL) {
26             return next;
27         } else {
28             next->right = right;
29             return recursive(right);
30         }
31     }
32 };

网上看到另一种递归的思路是：

假设左右子树已经flatten。

那么左子树root->left一直往右找到最后一个点p，把它指向右子树，p->right = root->right;

然后把root->right指向左子树root->left; 再把root-left 设置为空。

/**
 * 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 == NULL) return;
        flatten(root->left);
        flatten(root->right);
        if (root->left != NULL) {
            TreeNode* p = root->left;
            while (p->right != NULL) p = p->right;
            p->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }
    }
};

第一种思路应该比第二种高效。第二种即使左右子树都flatten了，还要一直找到左子树的最后一个结点。这个当左子树很大的时候，开销就会很大。