leetcode/cpp/0114.cpp at master · xfmeng17/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  void flatten(TreeNode *root) { func1(root); }

  //** in palce, T(n) = 2T(n) + n/2 => O(nlgn)
  void func1(TreeNode *root) { root = helper1(root); }
  TreeNode *helper1(TreeNode *root) {
    if (root == NULL) {
      return NULL;
    }
    TreeNode *left = root->left;
    TreeNode *right = root->right;

    if (left == NULL && right == NULL) {
      return root;
    }

    TreeNode *newleft = helper1(left);
    TreeNode *newright = helper1(right);
    root->left = NULL;
    root->right = newleft;

    TreeNode *temp = root;
    while (temp->right != NULL) {
      temp = temp->right;
    }
    temp->right = newright;

    return root;
  }
};