C++LeetCode 구현(156.이 진 트 리 의 상하 전도)

[LeetCode]156.Binary Tree Upside Down 이 진 트 리 의 위아래 가 뒤 바 뀌 었 습 니 다.
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
Example:
Input: [1,2,3,4,5]
    1
/ \
2   3
/ \
4   5
Output: return the root of the binary tree [4,5,2,#,#,3,1]
   4
/ \
5   2
/ \
3   1  
Clarification:
Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
   1
/ \
2   3
/
4
\
5
The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].
이 문 제 는 이 진 트 리 한 그루 를 위아래 로 뒤 집어 놓 고 오른쪽 노드 가 비어 있 거나 반드시 대응 하 는 왼쪽 노드 가 있 는 것 을 제한 했다.상하 가 뒤 바 뀐 후에 원래 이 진 트 리 의 가장 왼쪽 부분 은 뿌리 노드 가 되 었 고 이에 대응 하 는 오른쪽 부분 은 왼쪽 부분 노드 가 되 었 다.그의 아버지 노드 는 오른쪽 부분 노드 가 되 었 고 시계 방향 으로 회전 하 는 것 과 같다.일반 나무의 문 제 는 모두 교체 와 재 귀 두 가지 해법 이 있 는데 이 문제 도 예 외 는 아니다.먼저 재 귀 하 는 해법 을 살 펴 보 자.하나의 뿌리 노드 에 있어 목 표 는 왼쪽 노드 를 뿌리 노드 로 바 꾸 는 것 이다.오른쪽 노드 는 왼쪽 노드 로 바 꾸 고 원래 의 뿌리 노드 는 오른쪽 노드 로 바 꾸 는 것 이다.먼저 이 노드 가 존재 하 는 지 판단 하고 왼쪽 노드 가 있 는 지 판단 하 는 것 이다.이 두 가지 조건 을 만족 시 키 지 않 으 면 바로 연결 하면 되 고 뒤 집 을 필요 가 없다.그러면 왼쪽 노드 에 재 귀 함 수 를 계속 호출 하고 가장 왼쪽 노드 에 도착 할 때 까지 뒤 집 습 니 다.가장 왼쪽 노드 를 뒤 집 은 후에 이전 왼쪽 노드 로 돌아 가서 계속 뒤 집 으 면 됩 니 다.전체 나 무 를 뒤 집 을 때 까지 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if (!root || !root->left) return root;
        TreeNode *l = root->left, *r = root->right;
        TreeNode *res = upsideDownBinaryTree(l);
        l->left = r;
        l->right = root;
        root->left = NULL;
        root->right = NULL;
        return res;
    }
};

다음은 우리 가 교체 하 는 방법 을 살 펴 보 겠 습 니 다.재 귀 방법 과 반대 되 는 경우 이것 은 위 에서 아래로 뒤 집기 시작 하여 가장 왼쪽 부분 으로 뒤 집 을 때 까지 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;
        while (cur) {
            next = cur->left;
            cur->left = tmp;
            tmp = cur->right;
            cur->right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/156
유사 한 제목:
Reverse Linked List
참고 자료:
https://leetcode.com/problems/binary-tree-upside-down/
https://leetcode.com/problems/binary-tree-upside-down/discuss/49412/Clean-Java-solution
https://leetcode.com/problems/binary-tree-upside-down/discuss/49432/Easy-O(n)-iteration-solution-Java
https://leetcode.com/problems/binary-tree-upside-down/discuss/49406/Java-recursive-(O(logn)-space)-and-iterative-solutions-(O(1)-space)-with-explanation-and-figure
C++구현 LeetCode(156.이 진 트 리 의 상하 전도)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 의 상하 전도 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!