[Leetcode] Inorder Successor in BST 二叉搜索树中序下一个

marek 发布于2019-08-14 12:36 / 1172人阅读

摘要：所以我们要找的上面，实际上是从目标节点向根节点回溯时，第一个比目标节点大的节点。

Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.

路径入栈法 复杂度

时间 O(N) 空间 O(N)

思路

题目给定根节点和目标节点。目标节点如果有右节点的情况比较好处理，我们只要返回它的右节点的最左边的节点就行了（右节点自己没有左节点时则是右节点本身）。如果目标节点没有右节点，说明比目标节点稍大的节点应该在上面，因为我们知道目标节点的左节点肯定是比目标节点要小的。

那怎么知道目标节点的上面是什么呢？这时就需要从根节点搜索到目标节点了。这里要注意的是，目标节点的父亲不一定比目标节点大，因为有可能目标节点的是其父亲的右孩子。所以我们要找的上面，实际上是从目标节点向根节点回溯时，第一个比目标节点大的节点。最差的情况下，如果回溯到根节点还是比目标节点要小的话，说明目标节点就是整个数最大的数了，这时候返回空。

那怎么实现目标节点向根节点回溯，这里用一个栈就行了，在我们寻找目标节点时，把路径上的节点都压入栈中。

代码

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack stk = new Stack();
        TreeNode curr = root;
        // 找到目标节点并把路径上的节点压入栈
        while(curr != p){
            stk.push(curr);
            if(curr.val > p.val){
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        // 如果目标节点有右节点，则找到其右节点的最左边的节点，就是下一个数
        if(curr.right != null){
            curr = curr.right;
            while(curr.left != null){
                curr = curr.left;
            }
            return curr;
        } else {
        // 如果没有右节点，pop栈找到第一个比目标节点大的节点
            while(!stk.isEmpty() && stk.peek().val < curr.val){
                stk.pop();
            }
            // 如果栈都pop空了还没有比目标节点大的，说明没有更大的了
            return stk.isEmpty() ? null : stk.pop();
        }
    }
}

超融合服务器专线服务树中序 Successor Inorder 用js制作一个搜索框

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64584.html

【LeetCode 二叉树专项】二叉搜索树中的中序后继（285）

摘要：解法二迭代中序遍历分析作者二叉搜索树的中序后继是中序遍历中当前节点之后最小的节点。文章目录 1. 题目1.1 示例1.2 说明1.3 限制 2....

ccj659 2021-11-24 09:39 评论0 收藏0
【LeetCode 二叉树专项】把二叉搜索树转换为累加树（538）

摘要：解法一中序遍历分析由于给定了二叉搜索树，因此首先考虑中序遍历，使用示例，我们先来分别看一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。这里还是使用示例，我们再来观察一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。 ...

xcold 2021-11-18 10:02 评论0 收藏0
LeetCode 272 Closest Binary Tree Traversal II 解题思路

摘要：原题网址题意在二叉搜索树当中找到离最近的个数。解题思路由于二叉搜索数的中序遍历是有序的，比如例子中的树，中序遍历为。原题网址：https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find k values in the BST that are closes...

Youngdze 2019-08-16 13:26 评论0 收藏0
[Leetcode] Binary Search Tree Iterator 二叉搜素树迭代器

摘要：代码先找到第一个节点，并把路径入栈栈为空时不再有下一个栈顶是待返回元素如果该元素有右节点，把它的右节点及右节点的所有左边节点都压入栈中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

shixinzhang 2019-08-14 12:36 评论0 收藏0
我理解的数据结构（五）—— 二分搜索树（Binary Search Tree）

摘要：我理解的数据结构五二分搜索树一二叉树和链表一样，动态数据结构具有唯一根节点每个节点最多有两个子节点每个节点最多有一个父节点具有天然的递归结构每个节点的左子树也是二叉树每个节点的右子树也是二叉树一个节点或者空也是二叉树二二分搜索树是二叉树每个我理解的数据结构（五）—— 二分搜索树（Binary Search Tree）一、二叉树和链表一样，动态数据结构具有唯一根节点每个节点最...

xeblog 2019-08-19 11:13 评论0 收藏0