C++ Solution with long code with O(n) Time Complexity


  • 0
    Y
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if(!root || !p)
                return NULL;
            TreeNode *ans = NULL;
            bool find_p = false;
            parent_nd = NULL;
            dfs(root, NULL, p, find_p);
            if(!find_p)
                return ans;
            if(!parent_nd){
                if(!root->right)
                    return ans;
                else{
                    ans = root->right;
                    while(ans->left){
                        ans = ans->left;
                    }
                    return ans;
                }
            }else{
                if(parent_nd->left == p){
                    if(p->right == NULL)
                        return parent_nd;
                    else{
                        ans = p->right;
                        while(ans->left){
                            ans = ans->left;
                        }
                        return ans;
                    }
                }else{
                    if(root->val < p->val){
                        if(p->right == NULL)
                            return ans;
                        else{
                            ans = p->right;
                            while(ans->left){
                                ans = ans->left;
                            }
                            return ans;
                        }
                    }else{
                        if(root == parent_nd)
                            return ans;
                        ans = root;
                        while(ans->left->val > p->val)
                            ans = ans->left;
                        return ans;
                    }
                }
            }
        }
        
    private:
        void dfs(TreeNode* cur, TreeNode* parent, TreeNode* p, bool &find_p){
            if(cur == p){
                find_p = true;
                parent_nd = parent;
                return ;
            }
            if(cur->left){
                dfs(cur->left, cur, p, find_p);
                if(find_p)
                    return ;
            }
            if(cur->right){
                dfs(cur->right, cur, p, find_p);
                if(find_p)
                    return ;
            }
        }
    private:
    TreeNode* parent_nd;
    };

  • 0

    O(lgn) is impossible. The desired node might be at depth n (I'm assuming with n you mean the number of nodes).


  • 0
    Y

    Oh, Yes, you are right. Thank you for telling me that!


  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.