285. Inorder Successor in BST

痛定思痛。 2023-06-01 12:53 10阅读 0赞

import java.util.*
    
    /**
     * Lock by Leetcode
     * 285. Inorder Successor in BST
     * https://www.lintcode.com/problem/inorder-successor-in-bst/description
     *
     * Given a binary search tree (See Definition) and a node in it,
     * find the in-order successor of that node in the BST.
    If the given node has no in-order successor in the tree, return null.
    
    Challenge
    O(h), where h is the height of the BST.
     */
    
    class TreeNode(var `val`: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }
    
    //inorder: root->left->right
    
    class Solution {
        fun inorderSuccessor(root_: TreeNode?, node: TreeNode): TreeNode? {
            var findIt = false
            var root = root_
            val stack = Stack<TreeNode>()
            stack.push(root)
            while (root != null || stack.size > 0) {
                if (root != null) {
                    stack.push(root)
                    root = root.left!!
                } else {
                    root = stack.pop()
                    if (findIt) {
                        return root
                    }
                    if (root.`val` == node.`val`) {
                        findIt = true//if found the node, the next node is the result
                    }
                    root = root.right
                }
            }
            return null
        }
    }

转载于:https://www.cnblogs.com/johnnyzhao/p/11117847.html

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode Top Interview Questions 285. Inorder Successor in BST (Java版; Medium)

[welcome to my blog][] LeetCode Top Interview Questions 285. Inorder Successor in BS

梦里梦外;/ 2023年07月03日 12:07/ 0 赞/ 30 阅读

相关 285. Inorder Successor in BST

import java.util. / Lock by Leetcode 285. Inorder Successor in

痛定思痛。/ 2023年06月01日 12:53/ 0 赞/ 11 阅读

相关 230 Kth Smallest Element in a BST

public static int kthSmallest(TreeNode root, int k) { Stack<TreeNod

向右看齐/ 2022年08月04日 11:44/ 0 赞/ 109 阅读

相关 Facebook 面试题 Binary tree inorder successor

> 给定一个二叉树，每一个结点都有指向其父节点的指针。求这个结点的inorder successor。对于这个问题，我们首先要搞明白什么是`inorder successo

电玩女神/ 2022年07月13日 10:59/ 0 赞/ 98 阅读

相关 [leetcode]-530. Minimum Absolute Difference in BST

![Center][]x 求BST树种节点绝对差值的最小值，由BST树的性质可知，中序遍历会得到一个有序数组，显然所求必然是有序数组中所有相邻两数差的最小值。利用递归算法，在

浅浅的花香味﹌/ 2022年06月18日 10:44/ 0 赞/ 205 阅读

相关 [leetcode]: 530. Minimum Absolute Difference in BST

1.题目描述 Given a binary search tree with non-negative values, find the minimum absolute

ゝ一世哀愁。/ 2022年06月16日 14:38/ 0 赞/ 229 阅读

相关 530. Minimum Absolute Difference in BST

原题链接： [https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/][ht

川长思鸟来/ 2022年05月29日 21:12/ 0 赞/ 219 阅读

相关 1115. Counting Nodes in a BST (30)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the followi

淡淡的烟草味﹌/ 2022年05月28日 13:37/ 0 赞/ 206 阅读

相关 LeetCode 510. Inorder Successor in BST II

原题链接在这里：[https://leetcode.com/problems/inorder-successor-in-bst-ii/][https_leetcode.com_

╰半夏微凉°/ 2021年12月16日 23:41/ 0 赞/ 236 阅读

相关 LeetCode 510. Inorder Successor in BST II

原题链接在这里：[https://leetcode.com/problems/inorder-successor-in-bst-ii/][https_leetcode.com_

浅浅的花香味﹌/ 2021年11月13日 15:34/ 0 赞/ 261 阅读