C++刷LeetCode（面试题 04.06. 后继者）【递归】

糖逗

题目描述：

1. 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
   
2. 
   
3. 如果指定节点没有对应的“下一个”节点，则返回null。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: root = [2,1,3], p = 1
   
8. 
   
9.   2
   
10. / \
    
11. 1   3
    
12. 
    
13. 输出: 2
    
14. 示例 2:
    
15. 
    
16. 输入: root = [5,3,6,2,4,null,null,1], p = 6
    
17. 
    
18.       5
    
19.      / \
    
20.     3   6
    
21.    / \
    
22.   2   4
    
23. /   
    
24. 1
    
25. 
    
26. 输出: null
    
27. 
    
28. 来源：力扣（LeetCode）
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
   
4.         //递归
   
5.         if(root == NULL){
   
6.             return NULL;
   
7.         }
   
8.         if(root -> val <= p -> val){
   
9.             return inorderSuccessor(root -> right, p);
   
10.         }else{
    
11.             TreeNode* store = inorderSuccessor(root -> left, p);
    
12.             if(store == NULL){
    
13.                 return root;
    
14.             }else{
    
15.                 return store;
    
16.             }
    
17.         }
    
18.     }
    
19. };

复制代码