Interview question 04.06 Successor DFS plus auxiliary variable traversal

Interview questions 04.06. The successor

Design an algorithm , Find the... Of the specified node in the binary search tree “ next ” node （ That is to say, the middle order follows ）.

If the specified node does not have a corresponding “ next ” node , Then return to null.

Example 1:

Input : root = [2,1,3], p = 1

2
/
1 3

Output : 2

Example 2:

Input : root = [5,3,6,2,4,null,null,1], p = 6

  5
 / \
3   6

/
2 4
/
1

Output : null

The solution code is as follows ：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int r;
struct TreeNode* re;
void order_search(struct TreeNode* root,struct TreeNode* p){
    
     if(root&&r!=2){
    
        order_search(root->left,p);
        if(r==1){
    
            re=root;
            r=2;
        }
        if(root==p&&r==0){
    
            r=1;
        }
      
        order_search(root->right,p);
        


     }
 }


struct TreeNode* inorderSuccessor(struct TreeNode* root, struct TreeNode* p){
    
    r=0;
    re=NULL;
    order_search(root,p);
    return re;
    

}