[leetcode]114.두 갈래 나무가 체인 시계로 전개되다

3807 단어 LeetCode
두 갈래 나무를 정해 제자리에서 체인 시계로 펼치세요.
예를 들어, 지정된 두 갈래 트리
    1
   / \
  2   5
 / \   \
3   4   6

다음으로 확장:
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

사고방식: 나무의 노드 위치를 조정하고 왼쪽 나무를 오른쪽 나무의 위치에 삽입한 다음에 오른쪽 나무를 연결한다.구체적인 절차: 1.뿌리 노드부터 훑어보고 왼쪽 트리가 존재하는지 판단하고 없으면 오른쪽 왼쪽 트리의 위치까지 오른쪽으로 훑어본다.2. 왼쪽 나무의 가장 오른쪽 노드temp를 찾아 뿌리 노드의 오른쪽 노드를temp의 오른쪽 노드에 연결한다.3. 뿌리 노드의 왼쪽 트리를 오른쪽 트리로 바꾸고 왼쪽 트리를 비우게 한 다음 뿌리 노드를 오른쪽으로 훑어보고 1단계로 돌아간다.
AC 코드: (C++)
class Solution {
   public:
    void flatten(TreeNode* root) {
        while (root != NULL) {
            if (root->left == NULL) {
                root = root->right;
            } else {
                TreeNode* temp = root->left;
                while (temp->right != NULL) temp = temp->right;
                temp->right = root->right;
                root->right = root->left;
                root->left = NULL;
                root = root->right;
            }
        }
    }
};

좋은 웹페이지 즐겨찾기