【LeetCode】114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

두 갈래 나무에게 앞의 순서대로 두 갈래 나무를 체인 시계로 만들어 달라고 하세요.
step1: 바늘이 뿌리 노드를 가리키면 먼저 뿌리 노드의 왼쪽 트리를 뿌리 노드의 오른쪽 트리에 걸고 왼쪽 트리는 마지막 원소(즉 4)가 원래 오른쪽 트리의 뿌리 노드 5를 가리키며 뿌리 노드의 왼쪽 트리는 공백을 가리킨다.
    1
     \
      2     
     / \   
    3   4
         \
          5
           \
            6

step2: 이때 바늘은 뿌리 노드의 오른쪽 나무 뿌리 노드 2를 가리키고 step1을 반복한다. 즉, 2의 왼쪽 나무를 2의 오른쪽 나무 위에 걸고 왼쪽 나무 마지막 원소가 2의 원래 오른쪽 나무 뿌리 노드 5, 2의 왼쪽 바늘을 비운다.
    1
     \
      2     
       \   
        3
         \
          4
           \
            5
             \
              6

코드는 다음과 같습니다.
/**
 * 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) {
        while(root!=NULL){
            if(root->left!=NULL){
                TreeNode* curr=root->left;
                while(curr->right!=NULL)
                    curr=curr->right;
                curr->right=root->right;
                root->right=root->left;
                root->left=NULL;
            }
            root=root->right;
        }
       
    }
};

인내심을 가지고 예에 따라 자세히 한 번 나누어라.

좋은 웹페이지 즐겨찾기