114. Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Flatten Binary Tree to Linked List - LeetCode

 

전위순회 된 트리의 root가 주어졌을 때, 이를 우편향 트리로 변경하는 문제다.

전위순회 이므로 node->left->right순으로 방문하며, node의 right는 node의 left의 최대 right(nullptr일때까지 반복) 보다 크므로, left의 최대 right 뒤에 right로 붙여준다.

 

그리고 node의 left를 right로 옮겨준다.

 

그리고 지금까지 해온걸 반복하다보면 left에 붙은 노드들도 다 동일하게 처리된다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode* node) {
        if (!node) {
            return;
        }
        
        if (node->left) {
            TreeNode* temp = node->left;
            while(temp->right) {
                temp = temp->right;
            }
            
            temp->right = node->right;
            node->right = node->left;
            node->left = nullptr;
        }
        
        solve(node->right);
    }
    
    void flatten(TreeNode* root) {
        solve(root);
    }
};