当前位置：网站首页>面试题 04.06. 后继者-dfs加辅助变量遍历

面试题 04.06. 后继者-dfs加辅助变量遍历

2022-07-16 01:14:00 【Mr Gao】

面试题 04.06. 后继者

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

2
/
1 3

输出: 2

示例 2:

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

  5
 / \
3   6

/
2 4
/
1

输出: null

解题代码如下：

/** * 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;
    

}
原网站

版权声明
本文为[Mr Gao]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43327597/article/details/125805854

边栏推荐

猜你喜欢

随机推荐