C++LeetCode 구현(114.이 진 트 리 를 링크 로 펼 치기)

[LeetCode]114.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
click to show hints.
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order trave
이 문 제 는 이 진 트 리 를 링크 로 펼 쳐 야 한다.펼 친 후에 형 성 된 링크 의 순서에 따라 선착순 으로 옮 겨 다 니 는 것 으로 분석 하면 수의 옮 겨 다 니 는 것 만으로 도 재 귀 와 비 재 귀 의 두 가지 방법 으로 해결 할 수 있다.여기 서 우리 도 두 가지 방법 으로 해결 할 수 있다.먼저 재 귀 버 전의 사 고 를 살 펴 보면 DFS 의 사 고 를 이용 하여 가장 왼쪽 부분 노드 를 찾 은 다음 에 그의 아버지 노드 로 돌아 가 그의 아버지 노드 와 오른쪽 부분 노드 를 끊 고 원래 의 왼쪽 부분 노드 를 아버지 노드 의 오른쪽 부분 노드 에 연결 한 다음 에 원래 의 오른쪽 부분 노드 를 새로운 오른쪽 부분 노드 의 오른쪽 부분 노드 에 연결 한 다음 에 위의 아버지 노드 로 돌아 가 똑 같은 조작 을 하 는 것 이다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    void flatten(TreeNode *root) {
        if (!root) return;
        if (root->left) flatten(root->left);
        if (root->right) flatten(root->right);
        TreeNode *tmp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

예 를 들 어 아래 의 이 진 트 리 에 대해 상기 알고리즘 의 변환 과정 은 다음 과 같다.

     1
    / \
   2   5
  / \   \
 3   4   6

     1
    / \
   2   5
    \   \
     3   6
      \    
       4

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

다음은 비 교체 버 전의 실현 을 살 펴 보 자.이 방법 은 뿌리 노드 부터 출발 하여 왼쪽 노드 가 존재 하 는 지 확인 하 는 것 이다.만약 에 존재 하면 뿌리 노드 와 오른쪽 노드 를 끊 고 왼쪽 노드 와 그 뒤의 모든 구 조 를 원래 의 오른쪽 노드 의 위치 로 연결 시 키 고 원래 의 오른쪽 노드 를 원 왼쪽 노드 의 맨 뒤의 오른쪽 노드 에 연결 한 다음 에 보 자.코드 는 다음 과 같 습 니 다:
해법 2:

class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode *cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode *p = cur->left;
                while (p->right) p = p->right;
                p->right = cur->right;
                cur->right = cur->left;
                cur->left = NULL;
            }
            cur = cur->right;
        }
    }
};

예 를 들 어 아래 의 이 진 트 리 에 대해 상기 알고리즘 의 변환 과정 은 다음 과 같다.

     1
    / \
   2   5
  / \   \
 3   4   6

   1
    \
     2
    / \
   3   4
        \
         5
          \
           6
           
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

앞 순서 교체 해법 은 다음 과 같다.
해법 3:

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            if (t->left) {
                TreeNode *r = t->left;
                while (r->right) r = r->right;
                r->right = t->right;
                t->right = t->left;
                t->left = NULL;
            }
            if (t->right) s.push(t->right);
        }
    }
};

이 문 제 는 중 서,후 서,층 서 를 옮 겨 다 니 는 순서 로 원 두 갈래 나 무 를 펼 칠 수 있 고 각각 해당 하 는 재 귀 와 비 재 귀 방법 이 있 으 며 관심 있 는 동 화 는 스스로 실현 할 수 있다.
Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/114
유사 한 제목:
Flatten a Multilevel Doubly Linked List
참고 자료:
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37182/my-recursive-solution-is-easy-and-clean
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/my-short-post-order-traversal-java-solution-for-share
C++구현 LeetCode(114.이 진 트 리 를 링크 로 펼 치 는 것)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 를 링크 로 펼 치 는 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!