栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

面试题 04.06. 后继者 ●●

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

面试题 04.06. 后继者 ●●

面试题 04.06. 后继者 ●● 描述

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

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

示例

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

题解 1. 中序遍历 栈

中序遍历时,用 pre 节点记录上一个节点,当某节点处的 pre 等于 p 时,则输出当前节点。

  • 时间复杂度:O(n),其中 n 是二叉搜索树的节点数。中序遍历最多需要访问二叉搜索树中的每个节点一次。
  • 空间复杂度:O(n),其中 n 是二叉搜索树的节点数。空间复杂度取决于栈深度,平均情况是 O ( log ⁡ n ) O(log n) O(logn),最坏情况是 O(n)。
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(root == NULL) return NULL;
        stack st;
        TreeNode* curr = root;
        TreeNode* pre = NULL;
        while(!st.empty() || curr != NULL){
            if(curr != NULL){
                st.push(curr);
                curr = curr->left;		// 找到当前节点下的最左孩子
            }else{
                curr = st.top();		// 中
                st.pop();
                if(pre == p) return curr;
                pre = curr;
                curr = curr->right;		// 右
            }
        }
        return NULL;
    }
};
  • 第二种类似写法
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(root == NULL) return NULL;
        TreeNode* curr = root;
        TreeNode* pre = NULL;
        stack st;
        while(curr != NULL || !st.empty()){
            while(curr){
                st.push(curr);
                curr = curr->left;		// 找到当前节点下的最左孩子
            }
            curr = st.top();			// 中
            st.pop();
            if(pre == p) return curr;
            pre = curr;
            curr = curr->right;			// 右
        }
        return NULL;
    }
};
2. 中序遍历 递归

中序遍历时,用 pre 节点记录上一个节点,当某节点处的 pre 等于 p 时,则输出当前节点。

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* inorderSuccessor(TreeNode* curr, TreeNode* p){
        if(curr == NULL) return NULL;
        TreeNode* left = inorderSuccessor(curr->left, p);       // 左
        if(left != NULL) return left;   
        if(pre == p) return curr;                               // 中
        pre = curr;
        TreeNode* right = inorderSuccessor(curr->right, p);     // 右
        if(right != NULL) return right;
        return NULL;
    }
};
3. 搜索二叉树性质

二叉搜索树的一个性质是中序遍历序列单调递增,因此二叉搜索树中的节点 p 的后继节点是 val 大于 p->val 的最小节点。

  • 若 p->right != NULL,则节点 p 的中序后继在其右子树中,在其右子树中定位到最左边的节点,即为节点 p 的中序后继。
  • 若 p->right == NULL,则需要从根节点开始遍历寻找 val 大于 p->val 的最小节点。
    (1)初始 curr = root,然后每次比较 curr->val 和 p->val 的大小:
    (2) 若 curr->val > p->val,则 p 的后继可能是 curr 或在 curr 的左子树中,因此用 curr 更新答案,并将 curr 移动到其左子节点继续遍历;
    (3)若 curr->val <= p->val,则 p 的后继可能在 curr 的右子树中,因此将 curr 移动到其右子节点继续遍历。

  • 时间复杂度:O(n),其中 n 是二叉搜索树的节点数。遍历的节点数不超过二叉搜索树的高度,平均情况是 O(logn),最坏情况是 O(n)。
  • 空间复杂度:O(1)。
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p){
        if(root == NULL) return NULL;
        TreeNode* ans = NULL;
        if(p->right != NULL){           // 如果目标节点p有右子树
            ans = p->right;
            while(ans->left != NULL){   // 那么答案则在p右子树的最左节点处
                ans = ans->left;
            }
            return ans;
        }                           
        TreeNode* curr = root;          // p没有右子树
        while(curr != NULL){            // 找到大于p->val的最小节点
            if(curr->val > p->val){
                ans = curr;
                curr = curr->left;
            }else{
                curr = curr->right;
            }
        }
        return ans;
    }
};
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/939917.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号