Leetcode--두 갈래 나무를 체인 테이블로 전개

1430 단어 leetcode
From:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
두 갈래 나무를 정해 제자리에서 그것을 단일 체인 테이블로 전개한다.
 
예를 들어, 지정된 두 갈래 트리
1/\2 5/\3 4 6 확장:
1  \  2    \    3      \      4        \        5          \          6

생각


샘플의 결과를 보면 체인표는 두 갈래 나무의 앞순서가 두루 흐르는 결과이다.
그러나 만약에 앞의 순서에 따라 두 갈래 나무를 두루 훑어보았다면 노드는 그것의right 노드(체인 테이블의 노드의 다음 노드)가 어디를 가리키는지 예측할 수 없다.
거꾸로 훑어보면 훑어보는 순서가 6, 5, 4, 3, 2, 1이 되면 한 노드를 지나갈 때마다 저장하고 다음 노드에 도착할 때 선구 노드가 된다.
이 사고방식은 바로 뒷차례가 두루 돌아다니는 것이고, 두루 돌아다니는 순서는 오른쪽 왼쪽 중간이다
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //  
    TreeNode* pre;
    void flat(TreeNode* root){
        //  ， 
        if(root== NULL) return ;

        //  ， 
        flat(root->right);
        flat(root->left);

        // pre ， 
        if(pre== NULL)
            pre= root;
        else{
            //  
            root->left= NULL;
            root->right= pre;
            pre= root;
        }
    }
    void flatten(TreeNode* root) {
        pre= NULL;
        flat(root);
    }
};

두 갈래 나무의 최대 깊이 (python 구현)
흔히 볼 수 있는 면접 알고리즘 문제: 두 갈래 나무의 최대 깊이, 최소 깊이

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage