알고리즘 문제 - 두 갈래 나무 결점의 중차적 역행 후계 결점

제목: 두 갈래 나무의 결점을 제시하고 그 중 순서를 반복하는 다음 결점을 되돌려줍니다.
 
생각:
아버지를 가리키는 결점이 있다면:

만약에 현재 결점에 오른쪽 아들이 있거나 현재 결점이 뿌리 결점이라면 후계 결점은 오른쪽 나무의 가장 왼쪽 잎 노드이다

그렇지 않으면 현재 결점이 부결점의 왼쪽 아들이면 후계 결점이 부결점이다.(사실은 세 번째 상황의 특례, 즉 자신이 0대 조상이고 1대 조상으로 돌아가는 것이다)

그렇지 않으면 위로 옮겨다니며 n-1대 조상이 n대 조상의 왼쪽 아들일 때까지 n대 조상의 뒤를 잇는 결점은 n대 조상이다.또는 루트 노드를 두루 훑어본 후 부합되는 n대 결점을 찾지 못하면 이 결점은 중서 두루 훑어본 마지막 결점으로 후계가 없다..

시간 복잡도는 트리의 높이 O(lgN)입니다.
코드:

 1 // 

 2 struct TreeNode  3 {  4     int value;  5     TreeNode *parent;  6     TreeNode *left;  7     TreeNode *right;  8 };  9 

10 TreeNode *inorderSuccessor(TreeNode *node) 11 { 12     if(node == NULL) 13         return NULL; 14 

15     TreeNode *successor = NULL; 16 

17     if(node->right != NULL || node->parent == NULL)  // ， ， 

18  { 19         successor = node->right; 20         while(successor != NULL && successor->left != NULL)  // ， 

21  { 22             successor = successor->left; 23  } 24  } 25     else

26  { 27         while( (successor = node->parent) != NULL ) 28  { 29             if(successor->left == node)     // ， 

30  { 31                 break; 32  } 33             node = successor;       // 

34  } 35  } 36 

37     return successor; 38 }

 
만약 아버지의 결점을 가리키는 지침이 없다면 반드시 뿌리 노드를 정해야 한다.중간 순서로 두 갈래 나무를 훑어보고 창고로 비귀속 훑어보기;cur_로pop는 현재 창고의 결점을 가리키고prev는 이전 창고의 결점을 가리킨다.prev_pop이 결점을 입력할 때cur_pop은 바로 구하는 후계 결점이다.시간 복잡도는 O(N)입니다.
코드:

 1 // 

 2 struct TreeNode  3 {  4     int value;  5     TreeNode *left;  6     TreeNode *right;  7 };  8 

 9 TreeNode *inorderSuccessor(TreeNode *root, TreeNode *node) // ， ， 

10 { 11     if(root == NULL || node == NULL) 12         return NULL; 13 

14     stack<TreeNode *> tns; 15  tns.push(root); 16 

17     TreeNode *prev_pop, *cur_pop = NULL;    //prev_pop ，cur_pop 

18     TreeNode *ptn = root->left;             //ptn， 

19 

20     while( !tns.empty() || ptn != NULL ) 21  { 22         if(ptn != NULL)         // ， 

23  { 24  tns.push(ptn); 25             ptn = ptn->left; 26  } 27         else

28  { 29             prev_pop = cur_pop; 30             cur_pop  = tns.top(); 31             tns.pop();          // 

32 

33             if(prev_pop == node) 34                 break; 35 

36             ptn = cur_pop->right;   // 

37  } 38  } 39 

40     if(prev_pop == node)    // 

41         return cur_pop; 42     else

43         return NULL; 44 }