LeetCode114 Flatten Binary Tree to Linked List

제목 링크:


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

제목 설명:


두 갈래 나무를 단일 사슬표의 형식으로 바꾸면 단일 나뭇가지로 퇴화된다.
 
         1
        / \        2   5
      / \   \      3   4   6
 
           1
            \              2
              \                3
                \                  4
                  \                    5
                    \                      6

제목 분석:


순서대로 흐르는 변형을 관찰할 수 있다. 단지 나무로 변할 때 원 두 갈래 나무가 먼저 흐르는 순서대로 연결되는 것을 관찰할 수 있다.그래서 먼저 반복적으로 돌아갈 때 처리를 하고 두 갈래 나무의 노드를 다시 연결한다.대략적인 사고방식은 현재 뿌리 노드의 왼쪽 아이를 비우고, 오른쪽 아이는 원래의 왼쪽 아이를 가리키며, 원래의 왼쪽 아이의 마지막 오른쪽 아이(즉 빈 손가락 바늘 구역)는 뿌리 노드의 원래 오른쪽 아이를 가리킨다.

코드:

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

좋은 웹페이지 즐겨찾기