[LeetCode] 114. Flatten Binary Tree to Linked List 문제 풀이 보고서 (Python & C + + & Java)

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
목차
제목 설명
제목
풀이 방법
선착순
귀속
날짜
제목 주소:https://leetcode.com/problems/flatten-binary-tree-to-linked-list/#/description
제목 설명
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) 의 공간 복잡 도가 필요 하 다.
python 코드 는 다음 과 같 습 니 다:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        res = []
        self.preOrder(root, res)
        for i in range(len(res) - 1):
            res[i].left = None
            res[i].right = res[i + 1]
    
    def preOrder(self, root, res):
        if not root: return
        res.append(root)
        self.preOrder(root.left, res)
        self.preOrder(root.right, res)

귀착 하 다
재 귀 는 반드시 재 귀 함수 의 의 미 를 알 아야 한다. 나 는 재 귀 함수 의 입력 과 출력 이 무엇 인지 잘 모 르 면 정확 한 코드 를 쓸 수 없다 고 생각한다.
이 곳 의 flatten (root) 의 입력 은 나무의 뿌리 노드 입 니 다. 이 함 수 는 이 노드 아래 의 모든 아이들 이 먼저 옮 겨 다 니 는 순서에 따라 오른쪽 에 놓 습 니 다.되 돌아 오 는 것 은 비어 있 지만 이 함수 가 실 행 된 후에 도 루트 의 지향 은 원래 의 위치, 즉 나무의 뿌리 노드 입 니 다.
그래서 재 귀적 인 사고방식 이 생 겼 다. 좌우 자 나 무 를 각각 flatten 으로 두 개의 체인 시 계 를 형성 한 다음 에 뿌리 노드 의 왼쪽 아 이 를 뿌리 노드 의 오른쪽 아이 에 놓는다.원래 의 뿌리 노드 의 오른쪽 아 이 를 현재 뿌리 노드 링크 의 끝 에 맞 춥 니 다.
도형 화 설명:

     1
    / \
   2   5
  / \   \
 3   4   6

변환:

     1
      \
   2   5
    \   \
 3   4   6

2 는 루트, 3 은 left, 4 는 right.아래 와 같이 수정:
다시:

     1
      \
   2   5
    \   \
     3   6
      \   
       4       

다시:

     1
      \   
       2   
        \   
         3   
          \   
           4    
            \
             5
              \
               6

python 코드:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if not root: return
        left = root.left
        right = root.right
        root.left = None
        self.flatten(left)
        self.flatten(right)
        root.right = left
        cur = root
        while root.right:
            root = root.right
        root.right = right

C + + 코드:

/**
 * 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) {
        if (!root) return;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        root->left = nullptr;
        flatten(left);
        flatten(right);
        root->right = left;
        TreeNode* cur = root;
        while (cur->right)
            cur = cur->right;
        cur->right = right;
    }
};

Java 코드:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        flatten(left);
        flatten(right);
        root.right = left;
        TreeNode cur = root;
        while(cur.right != null){
            cur = cur.right;
        }
        cur.right = right;
    }
}

날짜.
2017 년 4 월 19 일 2019 년 1 월 7 일 - 새로운 한 주가 시 작 됩 니 다.