114. Flatten Binary Tree to Linked List (이 진 트 리 체인 테이블)

114. Flatten Binary Tree to Linked List (이 진 트 리 체인 테이블)
더 많은 내용 보기, 접근 가능:http://www.growai.cn
1. 문제 설명
Given a binary tree, flatten it to a linked list in-place.
이 진 트 리 를 지정 하여 이 진 트 리 를 제자리 (in - place) 에서 단일 체인 시트 로 변환 합 니 다.단일 체인 표 의 노드 순 서 는 이 진 트 리 앞 순 서 를 옮 겨 다 니 는 순서 입 니 다.
For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

2. C + + 구현 1 (vector 기반, 이 방법 은 접지 변환 이 아 닙 니 다)

//         ，    vector 
class Solution {
public:
    void flatten(TreeNode* root) {
        vector result;
        preorder(root, result);

        for(int i=1; ileft = NULL;
            result[i-1]->right = result[i];
        }

    }

private:
    void preorder(TreeNode* node, vector &res) {
        if(!node)
            return;
        res.push_back(node);
        preorder(node->left, res);
        preorder(node->right, res);
    }
};

3. C + + 구현 2

// node          ，     left     ，              
// left_last，    right      ，             right_last，
//   node         ，left_last right  ，    right_last    。

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* last = NULL;
        preorder(root, last);
    }
private:
    void preorder(TreeNode* node, TreeNode* &last) {
        if(!node)
            return;

        if(!node->left && !node->right) {
            last = node;
            return;
        }

        TreeNode* left = node->left;
        TreeNode* right = node->right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL;

        if(left) {
            preorder(left, left_last);
            node->left = NULL;
            node->right = left;
            last = left_last;
        }

        if(right) {
            preorder(right, right_last);
            if(left_last)
                left_last->right = right;
            last = right_last;
        }
    }
};