[OJ.leetcode] flatten-binary-tree-to-linked-list

https://oj.leetcode.com/problems/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

/* 대충 구현하여도 O(n)에 다 수행가능함. "문제는 어떻게 하면 elegant하게 구현할 수 있을까?" preorder로 돌면서, 1) parent의 leftchild가 있을 경우, left subtree의 rightmost 를 가리키는 포인터를 하나 두고, 2) parent->right를 rightmost->right에 붙임. 3) left subtree를 parent->right에 붙임. 4) parent->left = NULL 처리. key는 rightmost를 어떻게 찾는냐가 문제를 푸는 관건. */ /** * 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) { while(root){ if(root->left) { TreeNode* temp = root->left; while(temp->right) { temp = temp->right; } temp->right = root->right; root->right = root->left; root->left = NULL; } root = root->right; } } };