侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归】后继者

GabrielxD
2022-05-16 / 0 评论 / 0 点赞 / 39 阅读 / 444 字 / 正在检测是否收录...

题目

面试题 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

解题

方法一:递归

思路

按照题目模拟,中序遍历并记录上一个节点,如果当前遍历到节点的上一个节点为 p 那么当前节点就是要求的节点。

代码

class Solution {
    TreeNode prev, target, ans;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        target = p;
        inorderTraversal(root);
        return ans;
    }

    public void inorderTraversal(TreeNode root) {
        if (root == null) return;
        inorderTraversal(root.left);
        if (prev == target) ans = root;
        prev = root;
        inorderTraversal(root.right);
    }
}

方法一:利用 BST 的特性

思路

由 BST 的特性可知,如果 指定节点(p)有右子树,其右子树的最左子节点就是它的中序后继节点(successor)。

否则也可以根据当前节点(node)值与指定节点(p)值的大小关系确定搜索方向:

  • 如果 node.val > p.val,把要求的中序后继节点置为 node ,向左子树(node.left)进行搜索。
  • 如果 node.val < p.val,向右子树(node.right)进行搜索。
  • 如果 node.val == p.val,说明中序后继节点一定在上一次遍历中被找到了,直接退出循环。

代码

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = p.right;
        if (successor != null) {
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }
        TreeNode node = root;
        while (node != null && node != p) {
            if (node.val > p.val) {
                successor = node;
                node = node.left;
            } else node = node.right;
        }
        return successor;
    }
}
0

评论区