题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        /*
        1.如果存在右子树，返回右子树左下结点

        2.不存在右子树，往上找
            (1)如果存在父节点，且该结点是父节点的右节点，则继续网上找，一直找到(2)情况存在

            (2)如果存在父节点，且该结点时父节点的左结点，则返回父节点
        */
        if(!p) return nullptr;
        if(p->right){
            auto tmp = p->right;
            while(tmp->left) tmp = tmp->left;
            return tmp;
        }else{
            while(p->father && p->father->right == p) p = p->father;
            return p->father;
        }

    }
};