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

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

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

 
생각:
예에서 알 수 있듯이 이것은 전차적으로 반복되는 체인표이다. 우리는 뿌리 노드에서 출발하여 먼저 왼쪽 나무를 훑어볼 수 있다.
왼쪽 트리가 비어 있지 않으면 왼쪽 트리를 오른쪽 트리로 옮겨 현재 뿌리 노드의 오른쪽 바늘이 왼쪽 트리를 가리키게 하고 이 왼쪽 트리의 오른쪽 노드를 찾아 오른쪽 노드의 오른쪽 바늘을 현재 노드의 원래 오른쪽 트리를 가리킨다.마지막으로 현재 노드의 왼쪽 트리를 비어 있습니다.
그리고 현재 노드의 오른쪽 하위 트리에 접근해서 상술한 조작을 반복적으로 실행하면 된다.
코드는 다음과 같습니다.
/**
 * 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 preOrder(TreeNode* root){ 
        if(NULL != root->left){
            TreeNode* leftNode = root->left;
            TreeNode* right = root->right;
            root->left = NULL;
            root->right = leftNode;
            while(NULL != leftNode->right) leftNode = leftNode->right;
            leftNode->right = right;
            
            if(NULL == root->right)
                return;
            else
                preOrder(root->right);
        }
        
        if(NULL != root->right){
            preOrder(root->right);
        }
        
    }
    
    void flatten(TreeNode* root) {
        if(NULL == root)
            return;
        
        preOrder(root);
        return;
    }
};

좋은 웹페이지 즐겨찾기